/src/openssl/crypto/bn/bn_rand.c
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | * Copyright 1995-2024 The OpenSSL Project Authors. All Rights Reserved. |
3 | | * |
4 | | * Licensed under the Apache License 2.0 (the "License"). You may not use |
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 |
8 | | */ |
9 | | |
10 | | #include <stdio.h> |
11 | | #include <time.h> |
12 | | #include "internal/cryptlib.h" |
13 | | #include "crypto/rand.h" |
14 | | #include "bn_local.h" |
15 | | #include <openssl/rand.h> |
16 | | #include <openssl/sha.h> |
17 | | #include <openssl/evp.h> |
18 | | |
19 | | typedef enum bnrand_flag_e { |
20 | | NORMAL, TESTING, PRIVATE |
21 | | } BNRAND_FLAG; |
22 | | |
23 | | static int bnrand(BNRAND_FLAG flag, BIGNUM *rnd, int bits, int top, int bottom, |
24 | | unsigned int strength, BN_CTX *ctx) |
25 | 72.3k | { |
26 | 72.3k | unsigned char *buf = NULL; |
27 | 72.3k | int b, ret = 0, bit, bytes, mask; |
28 | 72.3k | OSSL_LIB_CTX *libctx = ossl_bn_get_libctx(ctx); |
29 | | |
30 | 72.3k | if (bits == 0) { |
31 | 0 | if (top != BN_RAND_TOP_ANY || bottom != BN_RAND_BOTTOM_ANY) |
32 | 0 | goto toosmall; |
33 | 0 | BN_zero(rnd); |
34 | 0 | return 1; |
35 | 0 | } |
36 | 72.3k | if (bits < 0 || (bits == 1 && top > 0)) |
37 | 0 | goto toosmall; |
38 | | |
39 | 72.3k | bytes = (bits + 7) / 8; |
40 | 72.3k | bit = (bits - 1) % 8; |
41 | 72.3k | mask = 0xff << (bit + 1); |
42 | | |
43 | 72.3k | buf = OPENSSL_malloc(bytes); |
44 | 72.3k | if (buf == NULL) |
45 | 0 | goto err; |
46 | | |
47 | | /* make a random number and set the top and bottom bits */ |
48 | 72.3k | b = flag == NORMAL ? RAND_bytes_ex(libctx, buf, bytes, strength) |
49 | 72.3k | : RAND_priv_bytes_ex(libctx, buf, bytes, strength); |
50 | 72.3k | if (b <= 0) |
51 | 0 | goto err; |
52 | | |
53 | 72.3k | if (flag == TESTING) { |
54 | | /* |
55 | | * generate patterns that are more likely to trigger BN library bugs |
56 | | */ |
57 | 0 | int i; |
58 | 0 | unsigned char c; |
59 | |
|
60 | 0 | for (i = 0; i < bytes; i++) { |
61 | 0 | if (RAND_bytes_ex(libctx, &c, 1, strength) <= 0) |
62 | 0 | goto err; |
63 | 0 | if (c >= 128 && i > 0) |
64 | 0 | buf[i] = buf[i - 1]; |
65 | 0 | else if (c < 42) |
66 | 0 | buf[i] = 0; |
67 | 0 | else if (c < 84) |
68 | 0 | buf[i] = 255; |
69 | 0 | } |
70 | 0 | } |
71 | | |
72 | 72.3k | if (top >= 0) { |
73 | 235 | if (top) { |
74 | 0 | if (bit == 0) { |
75 | 0 | buf[0] = 1; |
76 | 0 | buf[1] |= 0x80; |
77 | 0 | } else { |
78 | 0 | buf[0] |= (3 << (bit - 1)); |
79 | 0 | } |
80 | 235 | } else { |
81 | 235 | buf[0] |= (1 << bit); |
82 | 235 | } |
83 | 235 | } |
84 | 72.3k | buf[0] &= ~mask; |
85 | 72.3k | if (bottom) /* set bottom bit if requested */ |
86 | 0 | buf[bytes - 1] |= 1; |
87 | 72.3k | if (!BN_bin2bn(buf, bytes, rnd)) |
88 | 0 | goto err; |
89 | 72.3k | ret = 1; |
90 | 72.3k | err: |
91 | 72.3k | OPENSSL_clear_free(buf, bytes); |
92 | 72.3k | bn_check_top(rnd); |
93 | 72.3k | return ret; |
94 | | |
95 | 0 | toosmall: |
96 | 0 | ERR_raise(ERR_LIB_BN, BN_R_BITS_TOO_SMALL); |
97 | 0 | return 0; |
98 | 72.3k | } |
99 | | |
100 | | int BN_rand_ex(BIGNUM *rnd, int bits, int top, int bottom, |
101 | | unsigned int strength, BN_CTX *ctx) |
102 | 0 | { |
103 | 0 | return bnrand(NORMAL, rnd, bits, top, bottom, strength, ctx); |
104 | 0 | } |
105 | | #ifndef FIPS_MODULE |
106 | | int BN_rand(BIGNUM *rnd, int bits, int top, int bottom) |
107 | 0 | { |
108 | 0 | return bnrand(NORMAL, rnd, bits, top, bottom, 0, NULL); |
109 | 0 | } |
110 | | |
111 | | int BN_bntest_rand(BIGNUM *rnd, int bits, int top, int bottom) |
112 | 0 | { |
113 | 0 | return bnrand(TESTING, rnd, bits, top, bottom, 0, NULL); |
114 | 0 | } |
115 | | #endif |
116 | | |
117 | | int BN_priv_rand_ex(BIGNUM *rnd, int bits, int top, int bottom, |
118 | | unsigned int strength, BN_CTX *ctx) |
119 | 235 | { |
120 | 235 | return bnrand(PRIVATE, rnd, bits, top, bottom, strength, ctx); |
121 | 235 | } |
122 | | |
123 | | #ifndef FIPS_MODULE |
124 | | int BN_priv_rand(BIGNUM *rnd, int bits, int top, int bottom) |
125 | 0 | { |
126 | 0 | return bnrand(PRIVATE, rnd, bits, top, bottom, 0, NULL); |
127 | 0 | } |
128 | | #endif |
129 | | |
130 | | /* random number r: 0 <= r < range */ |
131 | | static int bnrand_range(BNRAND_FLAG flag, BIGNUM *r, const BIGNUM *range, |
132 | | unsigned int strength, BN_CTX *ctx) |
133 | 56.3k | { |
134 | 56.3k | int n; |
135 | 56.3k | int count = 100; |
136 | | |
137 | 56.3k | if (r == NULL) { |
138 | 0 | ERR_raise(ERR_LIB_BN, ERR_R_PASSED_NULL_PARAMETER); |
139 | 0 | return 0; |
140 | 0 | } |
141 | | |
142 | 56.3k | if (range->neg || BN_is_zero(range)) { |
143 | 0 | ERR_raise(ERR_LIB_BN, BN_R_INVALID_RANGE); |
144 | 0 | return 0; |
145 | 0 | } |
146 | | |
147 | 56.3k | n = BN_num_bits(range); /* n > 0 */ |
148 | | |
149 | | /* BN_is_bit_set(range, n - 1) always holds */ |
150 | | |
151 | 56.3k | if (n == 1) |
152 | 0 | BN_zero(r); |
153 | 56.3k | 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 | 19.6k | do { |
159 | 19.6k | if (!bnrand(flag, r, n + 1, BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY, |
160 | 19.6k | strength, ctx)) |
161 | 0 | return 0; |
162 | | |
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 | 19.6k | if (BN_cmp(r, range) >= 0) { |
170 | 14.4k | if (!BN_sub(r, r, range)) |
171 | 0 | return 0; |
172 | 14.4k | if (BN_cmp(r, range) >= 0) |
173 | 9.00k | if (!BN_sub(r, r, range)) |
174 | 0 | return 0; |
175 | 14.4k | } |
176 | | |
177 | 19.6k | if (!--count) { |
178 | 0 | ERR_raise(ERR_LIB_BN, BN_R_TOO_MANY_ITERATIONS); |
179 | 0 | return 0; |
180 | 0 | } |
181 | | |
182 | 19.6k | } |
183 | 19.6k | while (BN_cmp(r, range) >= 0); |
184 | 40.4k | } else { |
185 | 52.4k | do { |
186 | | /* range = 11..._2 or range = 101..._2 */ |
187 | 52.4k | if (!bnrand(flag, r, n, BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY, |
188 | 52.4k | strength, ctx)) |
189 | 0 | return 0; |
190 | | |
191 | 52.4k | if (!--count) { |
192 | 0 | ERR_raise(ERR_LIB_BN, BN_R_TOO_MANY_ITERATIONS); |
193 | 0 | return 0; |
194 | 0 | } |
195 | 52.4k | } |
196 | 52.4k | while (BN_cmp(r, range) >= 0); |
197 | 40.4k | } |
198 | | |
199 | 56.3k | bn_check_top(r); |
200 | 56.3k | return 1; |
201 | 56.3k | } |
202 | | |
203 | | int BN_rand_range_ex(BIGNUM *r, const BIGNUM *range, unsigned int strength, |
204 | | BN_CTX *ctx) |
205 | 0 | { |
206 | 0 | return bnrand_range(NORMAL, r, range, strength, ctx); |
207 | 0 | } |
208 | | |
209 | | #ifndef FIPS_MODULE |
210 | | int BN_rand_range(BIGNUM *r, const BIGNUM *range) |
211 | 0 | { |
212 | 0 | return bnrand_range(NORMAL, r, range, 0, NULL); |
213 | 0 | } |
214 | | #endif |
215 | | |
216 | | int BN_priv_rand_range_ex(BIGNUM *r, const BIGNUM *range, unsigned int strength, |
217 | | BN_CTX *ctx) |
218 | 56.3k | { |
219 | 56.3k | return bnrand_range(PRIVATE, r, range, strength, ctx); |
220 | 56.3k | } |
221 | | |
222 | | #ifndef FIPS_MODULE |
223 | | int BN_priv_rand_range(BIGNUM *r, const BIGNUM *range) |
224 | 0 | { |
225 | 0 | return bnrand_range(PRIVATE, r, range, 0, NULL); |
226 | 0 | } |
227 | | |
228 | | # ifndef OPENSSL_NO_DEPRECATED_3_0 |
229 | | int BN_pseudo_rand(BIGNUM *rnd, int bits, int top, int bottom) |
230 | 0 | { |
231 | 0 | return BN_rand(rnd, bits, top, bottom); |
232 | 0 | } |
233 | | |
234 | | int BN_pseudo_rand_range(BIGNUM *r, const BIGNUM *range) |
235 | 0 | { |
236 | 0 | return BN_rand_range(r, range); |
237 | 0 | } |
238 | | # endif |
239 | | #endif |
240 | | |
241 | | int ossl_bn_priv_rand_range_fixed_top(BIGNUM *r, const BIGNUM *range, |
242 | | unsigned int strength, BN_CTX *ctx) |
243 | 0 | { |
244 | 0 | int n; |
245 | 0 | int count = 100; |
246 | |
|
247 | 0 | if (r == NULL) { |
248 | 0 | ERR_raise(ERR_LIB_BN, ERR_R_PASSED_NULL_PARAMETER); |
249 | 0 | return 0; |
250 | 0 | } |
251 | | |
252 | 0 | if (range->neg || BN_is_zero(range)) { |
253 | 0 | ERR_raise(ERR_LIB_BN, BN_R_INVALID_RANGE); |
254 | 0 | return 0; |
255 | 0 | } |
256 | | |
257 | 0 | n = BN_num_bits(range); /* n > 0 */ |
258 | | |
259 | | /* BN_is_bit_set(range, n - 1) always holds */ |
260 | |
|
261 | 0 | if (n == 1) { |
262 | 0 | BN_zero(r); |
263 | 0 | } else { |
264 | 0 | BN_set_flags(r, BN_FLG_CONSTTIME); |
265 | 0 | do { |
266 | 0 | if (!bnrand(PRIVATE, r, n + 1, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY, |
267 | 0 | strength, ctx)) |
268 | 0 | return 0; |
269 | | |
270 | 0 | if (!--count) { |
271 | 0 | ERR_raise(ERR_LIB_BN, BN_R_TOO_MANY_ITERATIONS); |
272 | 0 | return 0; |
273 | 0 | } |
274 | 0 | ossl_bn_mask_bits_fixed_top(r, n); |
275 | 0 | } |
276 | 0 | while (BN_ucmp(r, range) >= 0); |
277 | | #ifdef BN_DEBUG |
278 | | /* With BN_DEBUG on a fixed top number cannot be returned */ |
279 | | bn_correct_top(r); |
280 | | #endif |
281 | 0 | } |
282 | | |
283 | 0 | return 1; |
284 | 0 | } |
285 | | |
286 | | /* |
287 | | * ossl_bn_gen_dsa_nonce_fixed_top generates a random number 0 <= out < range. |
288 | | * Unlike BN_rand_range, it also includes the contents of |priv| and |message| |
289 | | * in the generation so that an RNG failure isn't fatal as long as |priv| |
290 | | * remains secret. This is intended for use in DSA and ECDSA where an RNG |
291 | | * weakness leads directly to private key exposure unless this function is |
292 | | * used. |
293 | | */ |
294 | | int ossl_bn_gen_dsa_nonce_fixed_top(BIGNUM *out, const BIGNUM *range, |
295 | | const BIGNUM *priv, |
296 | | const unsigned char *message, |
297 | | size_t message_len, BN_CTX *ctx) |
298 | 0 | { |
299 | 0 | EVP_MD_CTX *mdctx = EVP_MD_CTX_new(); |
300 | | /* |
301 | | * We use 512 bits of random data per iteration to ensure that we have at |
302 | | * least |range| bits of randomness. |
303 | | */ |
304 | 0 | unsigned char random_bytes[64]; |
305 | 0 | unsigned char digest[SHA512_DIGEST_LENGTH]; |
306 | 0 | unsigned done, todo; |
307 | | /* We generate |range|+1 bytes of random output. */ |
308 | 0 | const unsigned num_k_bytes = BN_num_bytes(range) + 1; |
309 | 0 | unsigned char private_bytes[96]; |
310 | 0 | unsigned char *k_bytes = NULL; |
311 | 0 | const int max_n = 64; /* Pr(failure to generate) < 2^max_n */ |
312 | 0 | int n; |
313 | 0 | int ret = 0; |
314 | 0 | EVP_MD *md = NULL; |
315 | 0 | OSSL_LIB_CTX *libctx = ossl_bn_get_libctx(ctx); |
316 | |
|
317 | 0 | if (mdctx == NULL) |
318 | 0 | goto end; |
319 | | |
320 | 0 | k_bytes = OPENSSL_malloc(num_k_bytes); |
321 | 0 | if (k_bytes == NULL) |
322 | 0 | goto end; |
323 | | /* Ensure top byte is set to avoid non-constant time in bin2bn */ |
324 | 0 | k_bytes[0] = 0xff; |
325 | | |
326 | | /* We copy |priv| into a local buffer to avoid exposing its length. */ |
327 | 0 | if (BN_bn2binpad(priv, private_bytes, sizeof(private_bytes)) < 0) { |
328 | | /* |
329 | | * No reasonable DSA or ECDSA key should have a private key this |
330 | | * large and we don't handle this case in order to avoid leaking the |
331 | | * length of the private key. |
332 | | */ |
333 | 0 | ERR_raise(ERR_LIB_BN, BN_R_PRIVATE_KEY_TOO_LARGE); |
334 | 0 | goto end; |
335 | 0 | } |
336 | | |
337 | 0 | md = EVP_MD_fetch(libctx, "SHA512", NULL); |
338 | 0 | if (md == NULL) { |
339 | 0 | ERR_raise(ERR_LIB_BN, BN_R_NO_SUITABLE_DIGEST); |
340 | 0 | goto end; |
341 | 0 | } |
342 | 0 | for (n = 0; n < max_n; n++) { |
343 | 0 | unsigned char i = 0; |
344 | |
|
345 | 0 | for (done = 1; done < num_k_bytes;) { |
346 | 0 | if (RAND_priv_bytes_ex(libctx, random_bytes, sizeof(random_bytes), |
347 | 0 | 0) <= 0) |
348 | 0 | goto end; |
349 | | |
350 | 0 | if (!EVP_DigestInit_ex(mdctx, md, NULL) |
351 | 0 | || !EVP_DigestUpdate(mdctx, &i, sizeof(i)) |
352 | 0 | || !EVP_DigestUpdate(mdctx, private_bytes, |
353 | 0 | sizeof(private_bytes)) |
354 | 0 | || !EVP_DigestUpdate(mdctx, message, message_len) |
355 | 0 | || !EVP_DigestUpdate(mdctx, random_bytes, |
356 | 0 | sizeof(random_bytes)) |
357 | 0 | || !EVP_DigestFinal_ex(mdctx, digest, NULL)) |
358 | 0 | goto end; |
359 | | |
360 | 0 | todo = num_k_bytes - done; |
361 | 0 | if (todo > SHA512_DIGEST_LENGTH) |
362 | 0 | todo = SHA512_DIGEST_LENGTH; |
363 | 0 | memcpy(k_bytes + done, digest, todo); |
364 | 0 | done += todo; |
365 | 0 | ++i; |
366 | 0 | } |
367 | | |
368 | 0 | if (!BN_bin2bn(k_bytes, num_k_bytes, out)) |
369 | 0 | goto end; |
370 | | |
371 | | /* Clear out the top bits and rejection filter into range */ |
372 | 0 | BN_set_flags(out, BN_FLG_CONSTTIME); |
373 | 0 | ossl_bn_mask_bits_fixed_top(out, BN_num_bits(range)); |
374 | |
|
375 | 0 | if (BN_ucmp(out, range) < 0) { |
376 | 0 | ret = 1; |
377 | | #ifdef BN_DEBUG |
378 | | /* With BN_DEBUG on a fixed top number cannot be returned */ |
379 | | bn_correct_top(out); |
380 | | #endif |
381 | 0 | goto end; |
382 | 0 | } |
383 | 0 | } |
384 | | /* Failed to generate anything */ |
385 | 0 | ERR_raise(ERR_LIB_BN, ERR_R_INTERNAL_ERROR); |
386 | |
|
387 | 0 | end: |
388 | 0 | EVP_MD_CTX_free(mdctx); |
389 | 0 | EVP_MD_free(md); |
390 | 0 | OPENSSL_clear_free(k_bytes, num_k_bytes); |
391 | 0 | OPENSSL_cleanse(digest, sizeof(digest)); |
392 | 0 | OPENSSL_cleanse(random_bytes, sizeof(random_bytes)); |
393 | 0 | OPENSSL_cleanse(private_bytes, sizeof(private_bytes)); |
394 | 0 | return ret; |
395 | 0 | } |
396 | | |
397 | | int BN_generate_dsa_nonce(BIGNUM *out, const BIGNUM *range, |
398 | | const BIGNUM *priv, const unsigned char *message, |
399 | | size_t message_len, BN_CTX *ctx) |
400 | 0 | { |
401 | 0 | int ret; |
402 | |
|
403 | 0 | ret = ossl_bn_gen_dsa_nonce_fixed_top(out, range, priv, message, |
404 | 0 | message_len, ctx); |
405 | | /* |
406 | | * This call makes the BN_generate_dsa_nonce non-const-time, thus we |
407 | | * do not use it internally. But fixed_top BNs currently cannot be returned |
408 | | * from public API calls. |
409 | | */ |
410 | 0 | bn_correct_top(out); |
411 | 0 | return ret; |
412 | 0 | } |