]>
Commit | Line | Data |
---|---|---|
4f22f405 | 1 | /* |
da1c088f | 2 | * Copyright 1995-2023 The OpenSSL Project Authors. All Rights Reserved. |
983495c4 | 3 | * |
367ace68 | 4 | * Licensed under the Apache License 2.0 (the "License"). You may not use |
4f22f405 RS |
5 | * this file except in compliance with the License. You can obtain a copy |
6 | * in the file LICENSE in the source distribution or at | |
7 | * https://www.openssl.org/source/license.html | |
983495c4 | 8 | */ |
d02b48c6 RE |
9 | |
10 | #include <stdio.h> | |
11 | #include <time.h> | |
b39fc560 | 12 | #include "internal/cryptlib.h" |
25f2138b | 13 | #include "crypto/rand.h" |
706457b7 | 14 | #include "bn_local.h" |
ec577822 | 15 | #include <openssl/rand.h> |
8a99cb29 | 16 | #include <openssl/sha.h> |
9632bd0e | 17 | #include <openssl/evp.h> |
d02b48c6 | 18 | |
ddc6a5c8 RS |
19 | typedef enum bnrand_flag_e { |
20 | NORMAL, TESTING, PRIVATE | |
21 | } BNRAND_FLAG; | |
22 | ||
ee1d4f3d | 23 | static int bnrand(BNRAND_FLAG flag, BIGNUM *rnd, int bits, int top, int bottom, |
508258ca | 24 | unsigned int strength, BN_CTX *ctx) |
0f113f3e MC |
25 | { |
26 | unsigned char *buf = NULL; | |
ddc6a5c8 | 27 | int b, ret = 0, bit, bytes, mask; |
94553e85 | 28 | OSSL_LIB_CTX *libctx = ossl_bn_get_libctx(ctx); |
0f113f3e MC |
29 | |
30 | if (bits == 0) { | |
01c09f9f RS |
31 | if (top != BN_RAND_TOP_ANY || bottom != BN_RAND_BOTTOM_ANY) |
32 | goto toosmall; | |
0f113f3e MC |
33 | BN_zero(rnd); |
34 | return 1; | |
35 | } | |
01c09f9f RS |
36 | if (bits < 0 || (bits == 1 && top > 0)) |
37 | goto toosmall; | |
0f113f3e MC |
38 | |
39 | bytes = (bits + 7) / 8; | |
40 | bit = (bits - 1) % 8; | |
41 | mask = 0xff << (bit + 1); | |
42 | ||
b196e7d9 | 43 | buf = OPENSSL_malloc(bytes); |
e077455e | 44 | if (buf == NULL) |
0f113f3e | 45 | goto err; |
0f113f3e MC |
46 | |
47 | /* make a random number and set the top and bottom bits */ | |
508258ca P |
48 | b = flag == NORMAL ? RAND_bytes_ex(libctx, buf, bytes, strength) |
49 | : RAND_priv_bytes_ex(libctx, buf, bytes, strength); | |
ddc6a5c8 | 50 | if (b <= 0) |
e0a675e2 | 51 | goto err; |
38e33cef | 52 | |
ddc6a5c8 | 53 | if (flag == TESTING) { |
0f113f3e MC |
54 | /* |
55 | * generate patterns that are more likely to trigger BN library bugs | |
56 | */ | |
57 | int i; | |
58 | unsigned char c; | |
59 | ||
60 | for (i = 0; i < bytes; i++) { | |
508258ca | 61 | if (RAND_bytes_ex(libctx, &c, 1, strength) <= 0) |
266483d2 | 62 | goto err; |
0f113f3e MC |
63 | if (c >= 128 && i > 0) |
64 | buf[i] = buf[i - 1]; | |
65 | else if (c < 42) | |
66 | buf[i] = 0; | |
67 | else if (c < 84) | |
68 | buf[i] = 255; | |
69 | } | |
70 | } | |
111482cf | 71 | |
efee575a | 72 | if (top >= 0) { |
0f113f3e MC |
73 | if (top) { |
74 | if (bit == 0) { | |
75 | buf[0] = 1; | |
76 | buf[1] |= 0x80; | |
77 | } else { | |
78 | buf[0] |= (3 << (bit - 1)); | |
79 | } | |
80 | } else { | |
81 | buf[0] |= (1 << bit); | |
82 | } | |
83 | } | |
84 | buf[0] &= ~mask; | |
85 | if (bottom) /* set bottom bit if requested */ | |
86 | buf[bytes - 1] |= 1; | |
87 | if (!BN_bin2bn(buf, bytes, rnd)) | |
88 | goto err; | |
89 | ret = 1; | |
90 | err: | |
4b45c6e5 | 91 | OPENSSL_clear_free(buf, bytes); |
0f113f3e | 92 | bn_check_top(rnd); |
26a7d938 | 93 | return ret; |
01c09f9f RS |
94 | |
95 | toosmall: | |
9311d0c4 | 96 | ERR_raise(ERR_LIB_BN, BN_R_BITS_TOO_SMALL); |
01c09f9f | 97 | return 0; |
0f113f3e MC |
98 | } |
99 | ||
508258ca P |
100 | int BN_rand_ex(BIGNUM *rnd, int bits, int top, int bottom, |
101 | unsigned int strength, BN_CTX *ctx) | |
ee1d4f3d | 102 | { |
508258ca | 103 | return bnrand(NORMAL, rnd, bits, top, bottom, strength, ctx); |
ee1d4f3d | 104 | } |
f844f9eb | 105 | #ifndef FIPS_MODULE |
0f113f3e MC |
106 | int BN_rand(BIGNUM *rnd, int bits, int top, int bottom) |
107 | { | |
508258ca | 108 | return bnrand(NORMAL, rnd, bits, top, bottom, 0, NULL); |
0f113f3e MC |
109 | } |
110 | ||
0f113f3e MC |
111 | int BN_bntest_rand(BIGNUM *rnd, int bits, int top, int bottom) |
112 | { | |
508258ca | 113 | return bnrand(TESTING, rnd, bits, top, bottom, 0, NULL); |
ee1d4f3d | 114 | } |
2934be91 | 115 | #endif |
ee1d4f3d | 116 | |
508258ca P |
117 | int BN_priv_rand_ex(BIGNUM *rnd, int bits, int top, int bottom, |
118 | unsigned int strength, BN_CTX *ctx) | |
ee1d4f3d | 119 | { |
508258ca | 120 | return bnrand(PRIVATE, rnd, bits, top, bottom, strength, ctx); |
ddc6a5c8 RS |
121 | } |
122 | ||
f844f9eb | 123 | #ifndef FIPS_MODULE |
ddc6a5c8 RS |
124 | int BN_priv_rand(BIGNUM *rnd, int bits, int top, int bottom) |
125 | { | |
508258ca | 126 | return bnrand(PRIVATE, rnd, bits, top, bottom, 0, NULL); |
0f113f3e | 127 | } |
2934be91 | 128 | #endif |
57e7d3ce | 129 | |
e3068929 | 130 | /* random number r: 0 <= r < range */ |
ee1d4f3d | 131 | static int bnrand_range(BNRAND_FLAG flag, BIGNUM *r, const BIGNUM *range, |
508258ca | 132 | unsigned int strength, BN_CTX *ctx) |
0f113f3e | 133 | { |
3bc0ab06 | 134 | int n; |
0f113f3e MC |
135 | int count = 100; |
136 | ||
70f589ae | 137 | if (r == NULL) { |
138 | ERR_raise(ERR_LIB_BN, ERR_R_PASSED_NULL_PARAMETER); | |
139 | return 0; | |
140 | } | |
141 | ||
0f113f3e | 142 | if (range->neg || BN_is_zero(range)) { |
9311d0c4 | 143 | ERR_raise(ERR_LIB_BN, BN_R_INVALID_RANGE); |
0f113f3e MC |
144 | return 0; |
145 | } | |
146 | ||
147 | n = BN_num_bits(range); /* n > 0 */ | |
148 | ||
149 | /* BN_is_bit_set(range, n - 1) always holds */ | |
150 | ||
151 | if (n == 1) | |
152 | BN_zero(r); | |
153 | else if (!BN_is_bit_set(range, n - 2) && !BN_is_bit_set(range, n - 3)) { | |
154 | /* | |
155 | * range = 100..._2, so 3*range (= 11..._2) is exactly one bit longer | |
156 | * than range | |
157 | */ | |
158 | do { | |
ee1d4f3d | 159 | if (!bnrand(flag, r, n + 1, BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY, |
508258ca | 160 | strength, ctx)) |
0f113f3e | 161 | return 0; |
3bc0ab06 | 162 | |
0f113f3e MC |
163 | /* |
164 | * If r < 3*range, use r := r MOD range (which is either r, r - | |
165 | * range, or r - 2*range). Otherwise, iterate once more. Since | |
166 | * 3*range = 11..._2, each iteration succeeds with probability >= | |
167 | * .75. | |
168 | */ | |
169 | if (BN_cmp(r, range) >= 0) { | |
170 | if (!BN_sub(r, r, range)) | |
171 | return 0; | |
172 | if (BN_cmp(r, range) >= 0) | |
173 | if (!BN_sub(r, r, range)) | |
174 | return 0; | |
175 | } | |
176 | ||
177 | if (!--count) { | |
9311d0c4 | 178 | ERR_raise(ERR_LIB_BN, BN_R_TOO_MANY_ITERATIONS); |
0f113f3e MC |
179 | return 0; |
180 | } | |
181 | ||
182 | } | |
183 | while (BN_cmp(r, range) >= 0); | |
184 | } else { | |
185 | do { | |
186 | /* range = 11..._2 or range = 101..._2 */ | |
508258ca P |
187 | if (!bnrand(flag, r, n, BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY, 0, |
188 | ctx)) | |
0f113f3e MC |
189 | return 0; |
190 | ||
191 | if (!--count) { | |
9311d0c4 | 192 | ERR_raise(ERR_LIB_BN, BN_R_TOO_MANY_ITERATIONS); |
0f113f3e MC |
193 | return 0; |
194 | } | |
195 | } | |
196 | while (BN_cmp(r, range) >= 0); | |
197 | } | |
198 | ||
199 | bn_check_top(r); | |
200 | return 1; | |
201 | } | |
202 | ||
508258ca P |
203 | int BN_rand_range_ex(BIGNUM *r, const BIGNUM *range, unsigned int strength, |
204 | BN_CTX *ctx) | |
ee1d4f3d | 205 | { |
508258ca | 206 | return bnrand_range(NORMAL, r, range, strength, ctx); |
ee1d4f3d MC |
207 | } |
208 | ||
f844f9eb | 209 | #ifndef FIPS_MODULE |
ddc6a5c8 RS |
210 | int BN_rand_range(BIGNUM *r, const BIGNUM *range) |
211 | { | |
508258ca | 212 | return bnrand_range(NORMAL, r, range, 0, NULL); |
ee1d4f3d | 213 | } |
2934be91 | 214 | #endif |
ee1d4f3d | 215 | |
508258ca P |
216 | int BN_priv_rand_range_ex(BIGNUM *r, const BIGNUM *range, unsigned int strength, |
217 | BN_CTX *ctx) | |
ee1d4f3d | 218 | { |
508258ca | 219 | return bnrand_range(PRIVATE, r, range, strength, ctx); |
ddc6a5c8 RS |
220 | } |
221 | ||
f844f9eb | 222 | #ifndef FIPS_MODULE |
ddc6a5c8 RS |
223 | int BN_priv_rand_range(BIGNUM *r, const BIGNUM *range) |
224 | { | |
508258ca | 225 | return bnrand_range(PRIVATE, r, range, 0, NULL); |
ddc6a5c8 RS |
226 | } |
227 | ||
4d2a6159 | 228 | # ifndef OPENSSL_NO_DEPRECATED_3_0 |
5ecff87d | 229 | int BN_pseudo_rand(BIGNUM *rnd, int bits, int top, int bottom) |
0f113f3e | 230 | { |
5ecff87d | 231 | return BN_rand(rnd, bits, top, bottom); |
0f113f3e MC |
232 | } |
233 | ||
234 | int BN_pseudo_rand_range(BIGNUM *r, const BIGNUM *range) | |
235 | { | |
5ecff87d | 236 | return BN_rand_range(r, range); |
0f113f3e | 237 | } |
4d2a6159 | 238 | # endif |
2934be91 | 239 | #endif |
8a99cb29 | 240 | |
0f113f3e MC |
241 | /* |
242 | * BN_generate_dsa_nonce generates a random number 0 <= out < range. Unlike | |
243 | * BN_rand_range, it also includes the contents of |priv| and |message| in | |
244 | * the generation so that an RNG failure isn't fatal as long as |priv| | |
245 | * remains secret. This is intended for use in DSA and ECDSA where an RNG | |
246 | * weakness leads directly to private key exposure unless this function is | |
247 | * used. | |
248 | */ | |
249 | int BN_generate_dsa_nonce(BIGNUM *out, const BIGNUM *range, | |
250 | const BIGNUM *priv, const unsigned char *message, | |
251 | size_t message_len, BN_CTX *ctx) | |
252 | { | |
9632bd0e | 253 | EVP_MD_CTX *mdctx = EVP_MD_CTX_new(); |
0f113f3e MC |
254 | /* |
255 | * We use 512 bits of random data per iteration to ensure that we have at | |
256 | * least |range| bits of randomness. | |
257 | */ | |
258 | unsigned char random_bytes[64]; | |
259 | unsigned char digest[SHA512_DIGEST_LENGTH]; | |
260 | unsigned done, todo; | |
d7d1bdcb TM |
261 | /* We generate |range|+1 bytes of random output. */ |
262 | const unsigned num_k_bytes = BN_num_bytes(range) + 1; | |
0f113f3e | 263 | unsigned char private_bytes[96]; |
9632bd0e | 264 | unsigned char *k_bytes = NULL; |
d7d1bdcb TM |
265 | const int max_n = 64; /* Pr(failure to generate) < 2^max_n */ |
266 | int n; | |
0f113f3e | 267 | int ret = 0; |
9632bd0e | 268 | EVP_MD *md = NULL; |
94553e85 | 269 | OSSL_LIB_CTX *libctx = ossl_bn_get_libctx(ctx); |
9632bd0e | 270 | |
ee1d4f3d | 271 | if (mdctx == NULL) |
d7d1bdcb | 272 | goto end; |
0f113f3e MC |
273 | |
274 | k_bytes = OPENSSL_malloc(num_k_bytes); | |
90945fa3 | 275 | if (k_bytes == NULL) |
d7d1bdcb | 276 | goto end; |
0f113f3e MC |
277 | |
278 | /* We copy |priv| into a local buffer to avoid exposing its length. */ | |
31ca1940 | 279 | if (BN_bn2binpad(priv, private_bytes, sizeof(private_bytes)) < 0) { |
0f113f3e MC |
280 | /* |
281 | * No reasonable DSA or ECDSA key should have a private key this | |
282 | * large and we don't handle this case in order to avoid leaking the | |
283 | * length of the private key. | |
284 | */ | |
9311d0c4 | 285 | ERR_raise(ERR_LIB_BN, BN_R_PRIVATE_KEY_TOO_LARGE); |
d7d1bdcb | 286 | goto end; |
0f113f3e | 287 | } |
0f113f3e | 288 | |
9632bd0e MC |
289 | md = EVP_MD_fetch(libctx, "SHA512", NULL); |
290 | if (md == NULL) { | |
9311d0c4 | 291 | ERR_raise(ERR_LIB_BN, BN_R_NO_SUITABLE_DIGEST); |
d7d1bdcb | 292 | goto end; |
0f113f3e | 293 | } |
d7d1bdcb TM |
294 | for (n = 0; n < max_n; n++) { |
295 | for (done = 0; done < num_k_bytes;) { | |
296 | if (RAND_priv_bytes_ex(libctx, random_bytes, sizeof(random_bytes), | |
297 | 0) <= 0) | |
298 | goto end; | |
299 | ||
300 | if (!EVP_DigestInit_ex(mdctx, md, NULL) | |
301 | || !EVP_DigestUpdate(mdctx, &done, sizeof(done)) | |
302 | || !EVP_DigestUpdate(mdctx, private_bytes, | |
303 | sizeof(private_bytes)) | |
304 | || !EVP_DigestUpdate(mdctx, message, message_len) | |
305 | || !EVP_DigestUpdate(mdctx, random_bytes, | |
306 | sizeof(random_bytes)) | |
307 | || !EVP_DigestFinal_ex(mdctx, digest, NULL)) | |
308 | goto end; | |
309 | ||
310 | todo = num_k_bytes - done; | |
311 | if (todo > SHA512_DIGEST_LENGTH) | |
312 | todo = SHA512_DIGEST_LENGTH; | |
313 | memcpy(k_bytes + done, digest, todo); | |
314 | done += todo; | |
315 | } | |
0f113f3e | 316 | |
d7d1bdcb TM |
317 | /* Ensure top byte is set to avoid non-constant time in bin2bn */ |
318 | k_bytes[0] = 0x80; | |
319 | if (!BN_bin2bn(k_bytes, num_k_bytes, out)) | |
320 | goto end; | |
0f113f3e | 321 | |
d7d1bdcb TM |
322 | /* Clear out the top bits and rejection filter into range */ |
323 | BN_set_flags(out, BN_FLG_CONSTTIME | BN_FLG_FIXED_TOP); | |
324 | ossl_bn_mask_bits_fixed_top(out, BN_num_bits(range)); | |
325 | ||
326 | if (BN_ucmp(out, range) < 0) { | |
327 | ret = 1; | |
328 | goto end; | |
329 | } | |
330 | } | |
331 | /* Failed to generate anything */ | |
332 | ERR_raise(ERR_LIB_BN, ERR_R_INTERNAL_ERROR); | |
333 | ||
334 | end: | |
9632bd0e | 335 | EVP_MD_CTX_free(mdctx); |
3fd70262 | 336 | EVP_MD_free(md); |
177d433b | 337 | OPENSSL_clear_free(k_bytes, num_k_bytes); |
338 | OPENSSL_cleanse(digest, sizeof(digest)); | |
339 | OPENSSL_cleanse(random_bytes, sizeof(random_bytes)); | |
e5e71f28 | 340 | OPENSSL_cleanse(private_bytes, sizeof(private_bytes)); |
0f113f3e MC |
341 | return ret; |
342 | } |