diff options
Diffstat (limited to 'crypto/bn/bn_rand.c')
| -rw-r--r-- | crypto/bn/bn_rand.c | 255 |
1 files changed, 202 insertions, 53 deletions
diff --git a/crypto/bn/bn_rand.c b/crypto/bn/bn_rand.c index 6b4b50a068f1..ba0970b1f87d 100644 --- a/crypto/bn/bn_rand.c +++ b/crypto/bn/bn_rand.c @@ -1,7 +1,7 @@ /* - * Copyright 1995-2019 The OpenSSL Project Authors. All Rights Reserved. + * Copyright 1995-2024 The OpenSSL Project Authors. All Rights Reserved. * - * Licensed under the OpenSSL license (the "License"). You may not use + * Licensed under the Apache License 2.0 (the "License"). You may not use * this file except in compliance with the License. You can obtain a copy * in the file LICENSE in the source distribution or at * https://www.openssl.org/source/license.html @@ -10,18 +10,22 @@ #include <stdio.h> #include <time.h> #include "internal/cryptlib.h" +#include "crypto/rand.h" #include "bn_local.h" #include <openssl/rand.h> #include <openssl/sha.h> +#include <openssl/evp.h> typedef enum bnrand_flag_e { NORMAL, TESTING, PRIVATE } BNRAND_FLAG; -static int bnrand(BNRAND_FLAG flag, BIGNUM *rnd, int bits, int top, int bottom) +static int bnrand(BNRAND_FLAG flag, BIGNUM *rnd, int bits, int top, int bottom, + unsigned int strength, BN_CTX *ctx) { unsigned char *buf = NULL; int b, ret = 0, bit, bytes, mask; + OSSL_LIB_CTX *libctx = ossl_bn_get_libctx(ctx); if (bits == 0) { if (top != BN_RAND_TOP_ANY || bottom != BN_RAND_BOTTOM_ANY) @@ -38,12 +42,13 @@ static int bnrand(BNRAND_FLAG flag, BIGNUM *rnd, int bits, int top, int bottom) buf = OPENSSL_malloc(bytes); if (buf == NULL) { - BNerr(BN_F_BNRAND, ERR_R_MALLOC_FAILURE); + ERR_raise(ERR_LIB_BN, ERR_R_MALLOC_FAILURE); goto err; } /* make a random number and set the top and bottom bits */ - b = flag == NORMAL ? RAND_bytes(buf, bytes) : RAND_priv_bytes(buf, bytes); + b = flag == NORMAL ? RAND_bytes_ex(libctx, buf, bytes, strength) + : RAND_priv_bytes_ex(libctx, buf, bytes, strength); if (b <= 0) goto err; @@ -55,7 +60,7 @@ static int bnrand(BNRAND_FLAG flag, BIGNUM *rnd, int bits, int top, int bottom) unsigned char c; for (i = 0; i < bytes; i++) { - if (RAND_bytes(&c, 1) <= 0) + if (RAND_bytes_ex(libctx, &c, 1, strength) <= 0) goto err; if (c >= 128 && i > 0) buf[i] = buf[i - 1]; @@ -90,33 +95,54 @@ static int bnrand(BNRAND_FLAG flag, BIGNUM *rnd, int bits, int top, int bottom) return ret; toosmall: - BNerr(BN_F_BNRAND, BN_R_BITS_TOO_SMALL); + ERR_raise(ERR_LIB_BN, BN_R_BITS_TOO_SMALL); return 0; } +int BN_rand_ex(BIGNUM *rnd, int bits, int top, int bottom, + unsigned int strength, BN_CTX *ctx) +{ + return bnrand(NORMAL, rnd, bits, top, bottom, strength, ctx); +} +#ifndef FIPS_MODULE int BN_rand(BIGNUM *rnd, int bits, int top, int bottom) { - return bnrand(NORMAL, rnd, bits, top, bottom); + return bnrand(NORMAL, rnd, bits, top, bottom, 0, NULL); } int BN_bntest_rand(BIGNUM *rnd, int bits, int top, int bottom) { - return bnrand(TESTING, rnd, bits, top, bottom); + return bnrand(TESTING, rnd, bits, top, bottom, 0, NULL); +} +#endif + +int BN_priv_rand_ex(BIGNUM *rnd, int bits, int top, int bottom, + unsigned int strength, BN_CTX *ctx) +{ + return bnrand(PRIVATE, rnd, bits, top, bottom, strength, ctx); } +#ifndef FIPS_MODULE int BN_priv_rand(BIGNUM *rnd, int bits, int top, int bottom) { - return bnrand(PRIVATE, rnd, bits, top, bottom); + return bnrand(PRIVATE, rnd, bits, top, bottom, 0, NULL); } +#endif /* random number r: 0 <= r < range */ -static int bnrand_range(BNRAND_FLAG flag, BIGNUM *r, const BIGNUM *range) +static int bnrand_range(BNRAND_FLAG flag, BIGNUM *r, const BIGNUM *range, + unsigned int strength, BN_CTX *ctx) { int n; int count = 100; + if (r == NULL) { + ERR_raise(ERR_LIB_BN, ERR_R_PASSED_NULL_PARAMETER); + return 0; + } + if (range->neg || BN_is_zero(range)) { - BNerr(BN_F_BNRAND_RANGE, BN_R_INVALID_RANGE); + ERR_raise(ERR_LIB_BN, BN_R_INVALID_RANGE); return 0; } @@ -132,7 +158,8 @@ static int bnrand_range(BNRAND_FLAG flag, BIGNUM *r, const BIGNUM *range) * than range */ do { - if (!bnrand(flag, r, n + 1, BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY)) + if (!bnrand(flag, r, n + 1, BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY, + strength, ctx)) return 0; /* @@ -150,7 +177,7 @@ static int bnrand_range(BNRAND_FLAG flag, BIGNUM *r, const BIGNUM *range) } if (!--count) { - BNerr(BN_F_BNRAND_RANGE, BN_R_TOO_MANY_ITERATIONS); + ERR_raise(ERR_LIB_BN, BN_R_TOO_MANY_ITERATIONS); return 0; } @@ -159,11 +186,12 @@ static int bnrand_range(BNRAND_FLAG flag, BIGNUM *r, const BIGNUM *range) } else { do { /* range = 11..._2 or range = 101..._2 */ - if (!bnrand(flag, r, n, BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY)) + if (!bnrand(flag, r, n, BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY, + strength, ctx)) return 0; if (!--count) { - BNerr(BN_F_BNRAND_RANGE, BN_R_TOO_MANY_ITERATIONS); + ERR_raise(ERR_LIB_BN, BN_R_TOO_MANY_ITERATIONS); return 0; } } @@ -174,16 +202,32 @@ static int bnrand_range(BNRAND_FLAG flag, BIGNUM *r, const BIGNUM *range) return 1; } +int BN_rand_range_ex(BIGNUM *r, const BIGNUM *range, unsigned int strength, + BN_CTX *ctx) +{ + return bnrand_range(NORMAL, r, range, strength, ctx); +} + +#ifndef FIPS_MODULE int BN_rand_range(BIGNUM *r, const BIGNUM *range) { - return bnrand_range(NORMAL, r, range); + return bnrand_range(NORMAL, r, range, 0, NULL); +} +#endif + +int BN_priv_rand_range_ex(BIGNUM *r, const BIGNUM *range, unsigned int strength, + BN_CTX *ctx) +{ + return bnrand_range(PRIVATE, r, range, strength, ctx); } +#ifndef FIPS_MODULE int BN_priv_rand_range(BIGNUM *r, const BIGNUM *range) { - return bnrand_range(PRIVATE, r, range); + return bnrand_range(PRIVATE, r, range, 0, NULL); } +# ifndef OPENSSL_NO_DEPRECATED_3_0 int BN_pseudo_rand(BIGNUM *rnd, int bits, int top, int bottom) { return BN_rand(rnd, bits, top, bottom); @@ -193,20 +237,68 @@ int BN_pseudo_rand_range(BIGNUM *r, const BIGNUM *range) { return BN_rand_range(r, range); } +# endif +#endif + +int ossl_bn_priv_rand_range_fixed_top(BIGNUM *r, const BIGNUM *range, + unsigned int strength, BN_CTX *ctx) +{ + int n; + int count = 100; + + if (r == NULL) { + ERR_raise(ERR_LIB_BN, ERR_R_PASSED_NULL_PARAMETER); + return 0; + } + + if (range->neg || BN_is_zero(range)) { + ERR_raise(ERR_LIB_BN, BN_R_INVALID_RANGE); + return 0; + } + + n = BN_num_bits(range); /* n > 0 */ + + /* BN_is_bit_set(range, n - 1) always holds */ + + if (n == 1) { + BN_zero(r); + } else { + BN_set_flags(r, BN_FLG_CONSTTIME); + do { + if (!bnrand(PRIVATE, r, n + 1, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY, + strength, ctx)) + return 0; + + if (!--count) { + ERR_raise(ERR_LIB_BN, BN_R_TOO_MANY_ITERATIONS); + return 0; + } + ossl_bn_mask_bits_fixed_top(r, n); + } + while (BN_ucmp(r, range) >= 0); +#ifdef BN_DEBUG + /* With BN_DEBUG on a fixed top number cannot be returned */ + bn_correct_top(r); +#endif + } + + return 1; +} /* - * BN_generate_dsa_nonce generates a random number 0 <= out < range. Unlike - * BN_rand_range, it also includes the contents of |priv| and |message| in - * the generation so that an RNG failure isn't fatal as long as |priv| + * ossl_bn_gen_dsa_nonce_fixed_top generates a random number 0 <= out < range. + * Unlike BN_rand_range, it also includes the contents of |priv| and |message| + * in the generation so that an RNG failure isn't fatal as long as |priv| * remains secret. This is intended for use in DSA and ECDSA where an RNG * weakness leads directly to private key exposure unless this function is * used. */ -int BN_generate_dsa_nonce(BIGNUM *out, const BIGNUM *range, - const BIGNUM *priv, const unsigned char *message, - size_t message_len, BN_CTX *ctx) +int ossl_bn_gen_dsa_nonce_fixed_top(BIGNUM *out, const BIGNUM *range, + const BIGNUM *priv, + const unsigned char *message, + size_t message_len, BN_CTX *ctx) { - SHA512_CTX sha; + EVP_MD_CTX *mdctx = EVP_MD_CTX_new(); /* * We use 512 bits of random data per iteration to ensure that we have at * least |range| bits of randomness. @@ -214,15 +306,24 @@ int BN_generate_dsa_nonce(BIGNUM *out, const BIGNUM *range, unsigned char random_bytes[64]; unsigned char digest[SHA512_DIGEST_LENGTH]; unsigned done, todo; - /* We generate |range|+8 bytes of random output. */ - const unsigned num_k_bytes = BN_num_bytes(range) + 8; + /* We generate |range|+1 bytes of random output. */ + const unsigned num_k_bytes = BN_num_bytes(range) + 1; unsigned char private_bytes[96]; - unsigned char *k_bytes; + unsigned char *k_bytes = NULL; + const int max_n = 64; /* Pr(failure to generate) < 2^max_n */ + int n; int ret = 0; + EVP_MD *md = NULL; + OSSL_LIB_CTX *libctx = ossl_bn_get_libctx(ctx); + + if (mdctx == NULL) + goto end; k_bytes = OPENSSL_malloc(num_k_bytes); if (k_bytes == NULL) - goto err; + goto end; + /* Ensure top byte is set to avoid non-constant time in bin2bn */ + k_bytes[0] = 0xff; /* We copy |priv| into a local buffer to avoid exposing its length. */ if (BN_bn2binpad(priv, private_bytes, sizeof(private_bytes)) < 0) { @@ -231,35 +332,83 @@ int BN_generate_dsa_nonce(BIGNUM *out, const BIGNUM *range, * large and we don't handle this case in order to avoid leaking the * length of the private key. */ - BNerr(BN_F_BN_GENERATE_DSA_NONCE, BN_R_PRIVATE_KEY_TOO_LARGE); - goto err; + ERR_raise(ERR_LIB_BN, BN_R_PRIVATE_KEY_TOO_LARGE); + goto end; } - for (done = 0; done < num_k_bytes;) { - if (RAND_priv_bytes(random_bytes, sizeof(random_bytes)) != 1) - goto err; - SHA512_Init(&sha); - SHA512_Update(&sha, &done, sizeof(done)); - SHA512_Update(&sha, private_bytes, sizeof(private_bytes)); - SHA512_Update(&sha, message, message_len); - SHA512_Update(&sha, random_bytes, sizeof(random_bytes)); - SHA512_Final(digest, &sha); - - todo = num_k_bytes - done; - if (todo > SHA512_DIGEST_LENGTH) - todo = SHA512_DIGEST_LENGTH; - memcpy(k_bytes + done, digest, todo); - done += todo; + md = EVP_MD_fetch(libctx, "SHA512", NULL); + if (md == NULL) { + ERR_raise(ERR_LIB_BN, BN_R_NO_SUITABLE_DIGEST); + goto end; } + for (n = 0; n < max_n; n++) { + unsigned char i = 0; + + for (done = 1; done < num_k_bytes;) { + if (RAND_priv_bytes_ex(libctx, random_bytes, sizeof(random_bytes), + 0) <= 0) + goto end; + + if (!EVP_DigestInit_ex(mdctx, md, NULL) + || !EVP_DigestUpdate(mdctx, &i, sizeof(i)) + || !EVP_DigestUpdate(mdctx, private_bytes, + sizeof(private_bytes)) + || !EVP_DigestUpdate(mdctx, message, message_len) + || !EVP_DigestUpdate(mdctx, random_bytes, + sizeof(random_bytes)) + || !EVP_DigestFinal_ex(mdctx, digest, NULL)) + goto end; + + todo = num_k_bytes - done; + if (todo > SHA512_DIGEST_LENGTH) + todo = SHA512_DIGEST_LENGTH; + memcpy(k_bytes + done, digest, todo); + done += todo; + ++i; + } - if (!BN_bin2bn(k_bytes, num_k_bytes, out)) - goto err; - if (BN_mod(out, out, range, ctx) != 1) - goto err; - ret = 1; + if (!BN_bin2bn(k_bytes, num_k_bytes, out)) + goto end; - err: - OPENSSL_free(k_bytes); + /* Clear out the top bits and rejection filter into range */ + BN_set_flags(out, BN_FLG_CONSTTIME); + ossl_bn_mask_bits_fixed_top(out, BN_num_bits(range)); + + if (BN_ucmp(out, range) < 0) { + ret = 1; +#ifdef BN_DEBUG + /* With BN_DEBUG on a fixed top number cannot be returned */ + bn_correct_top(out); +#endif + goto end; + } + } + /* Failed to generate anything */ + ERR_raise(ERR_LIB_BN, ERR_R_INTERNAL_ERROR); + + end: + EVP_MD_CTX_free(mdctx); + EVP_MD_free(md); + OPENSSL_clear_free(k_bytes, num_k_bytes); + OPENSSL_cleanse(digest, sizeof(digest)); + OPENSSL_cleanse(random_bytes, sizeof(random_bytes)); OPENSSL_cleanse(private_bytes, sizeof(private_bytes)); return ret; } + +int BN_generate_dsa_nonce(BIGNUM *out, const BIGNUM *range, + const BIGNUM *priv, const unsigned char *message, + size_t message_len, BN_CTX *ctx) +{ + int ret; + + ret = ossl_bn_gen_dsa_nonce_fixed_top(out, range, priv, message, + message_len, ctx); + /* + * This call makes the BN_generate_dsa_nonce non-const-time, thus we + * do not use it internally. But fixed_top BNs currently cannot be returned + * from public API calls. + */ + bn_correct_top(out); + return ret; +} |