]>
Commit | Line | Data |
---|---|---|
4f22f405 | 1 | /* |
b0edda11 | 2 | * Copyright 1995-2018 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" |
ee1d4f3d | 13 | #include "internal/rand_int.h" |
d02b48c6 | 14 | #include "bn_lcl.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 MC |
23 | static int bnrand(BNRAND_FLAG flag, BIGNUM *rnd, int bits, int top, int bottom, |
24 | BN_CTX *ctx) | |
0f113f3e MC |
25 | { |
26 | unsigned char *buf = NULL; | |
ddc6a5c8 | 27 | int b, ret = 0, bit, bytes, mask; |
ee1d4f3d | 28 | OPENSSL_CTX *libctx = bn_get_lib_ctx(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); |
0f113f3e MC |
44 | if (buf == NULL) { |
45 | BNerr(BN_F_BNRAND, ERR_R_MALLOC_FAILURE); | |
46 | goto err; | |
47 | } | |
48 | ||
49 | /* make a random number and set the top and bottom bits */ | |
ee1d4f3d MC |
50 | b = flag == NORMAL ? rand_bytes_ex(libctx, buf, bytes) |
51 | : rand_priv_bytes_ex(libctx, buf, bytes); | |
ddc6a5c8 | 52 | if (b <= 0) |
e0a675e2 | 53 | goto err; |
38e33cef | 54 | |
ddc6a5c8 | 55 | if (flag == TESTING) { |
0f113f3e MC |
56 | /* |
57 | * generate patterns that are more likely to trigger BN library bugs | |
58 | */ | |
59 | int i; | |
60 | unsigned char c; | |
61 | ||
62 | for (i = 0; i < bytes; i++) { | |
ee1d4f3d | 63 | if (rand_bytes_ex(libctx, &c, 1) <= 0) |
266483d2 | 64 | goto err; |
0f113f3e MC |
65 | if (c >= 128 && i > 0) |
66 | buf[i] = buf[i - 1]; | |
67 | else if (c < 42) | |
68 | buf[i] = 0; | |
69 | else if (c < 84) | |
70 | buf[i] = 255; | |
71 | } | |
72 | } | |
111482cf | 73 | |
efee575a | 74 | if (top >= 0) { |
0f113f3e MC |
75 | if (top) { |
76 | if (bit == 0) { | |
77 | buf[0] = 1; | |
78 | buf[1] |= 0x80; | |
79 | } else { | |
80 | buf[0] |= (3 << (bit - 1)); | |
81 | } | |
82 | } else { | |
83 | buf[0] |= (1 << bit); | |
84 | } | |
85 | } | |
86 | buf[0] &= ~mask; | |
87 | if (bottom) /* set bottom bit if requested */ | |
88 | buf[bytes - 1] |= 1; | |
89 | if (!BN_bin2bn(buf, bytes, rnd)) | |
90 | goto err; | |
91 | ret = 1; | |
92 | err: | |
4b45c6e5 | 93 | OPENSSL_clear_free(buf, bytes); |
0f113f3e | 94 | bn_check_top(rnd); |
26a7d938 | 95 | return ret; |
01c09f9f RS |
96 | |
97 | toosmall: | |
98 | BNerr(BN_F_BNRAND, BN_R_BITS_TOO_SMALL); | |
99 | return 0; | |
0f113f3e MC |
100 | } |
101 | ||
ee1d4f3d MC |
102 | int BN_rand_ex(BIGNUM *rnd, int bits, int top, int bottom, BN_CTX *ctx) |
103 | { | |
104 | return bnrand(NORMAL, rnd, bits, top, bottom, ctx); | |
105 | } | |
2934be91 | 106 | #ifndef FIPS_MODE |
0f113f3e MC |
107 | int BN_rand(BIGNUM *rnd, int bits, int top, int bottom) |
108 | { | |
ee1d4f3d | 109 | return bnrand(NORMAL, rnd, bits, top, bottom, NULL); |
0f113f3e MC |
110 | } |
111 | ||
0f113f3e MC |
112 | int BN_bntest_rand(BIGNUM *rnd, int bits, int top, int bottom) |
113 | { | |
ee1d4f3d MC |
114 | return bnrand(TESTING, rnd, bits, top, bottom, NULL); |
115 | } | |
2934be91 | 116 | #endif |
ee1d4f3d MC |
117 | |
118 | int BN_priv_rand_ex(BIGNUM *rnd, int bits, int top, int bottom, BN_CTX *ctx) | |
119 | { | |
120 | return bnrand(PRIVATE, rnd, bits, top, bottom, ctx); | |
ddc6a5c8 RS |
121 | } |
122 | ||
2934be91 | 123 | #ifndef FIPS_MODE |
ddc6a5c8 RS |
124 | int BN_priv_rand(BIGNUM *rnd, int bits, int top, int bottom) |
125 | { | |
ee1d4f3d | 126 | return bnrand(PRIVATE, rnd, bits, top, bottom, NULL); |
0f113f3e | 127 | } |
2934be91 | 128 | #endif |
57e7d3ce | 129 | |
e3068929 | 130 | /* random number r: 0 <= r < range */ |
ee1d4f3d MC |
131 | static int bnrand_range(BNRAND_FLAG flag, BIGNUM *r, const BIGNUM *range, |
132 | BN_CTX *ctx) | |
0f113f3e | 133 | { |
3bc0ab06 | 134 | int n; |
0f113f3e MC |
135 | int count = 100; |
136 | ||
137 | if (range->neg || BN_is_zero(range)) { | |
ddc6a5c8 | 138 | BNerr(BN_F_BNRAND_RANGE, BN_R_INVALID_RANGE); |
0f113f3e MC |
139 | return 0; |
140 | } | |
141 | ||
142 | n = BN_num_bits(range); /* n > 0 */ | |
143 | ||
144 | /* BN_is_bit_set(range, n - 1) always holds */ | |
145 | ||
146 | if (n == 1) | |
147 | BN_zero(r); | |
148 | else if (!BN_is_bit_set(range, n - 2) && !BN_is_bit_set(range, n - 3)) { | |
149 | /* | |
150 | * range = 100..._2, so 3*range (= 11..._2) is exactly one bit longer | |
151 | * than range | |
152 | */ | |
153 | do { | |
ee1d4f3d MC |
154 | if (!bnrand(flag, r, n + 1, BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY, |
155 | ctx)) | |
0f113f3e | 156 | return 0; |
3bc0ab06 | 157 | |
0f113f3e MC |
158 | /* |
159 | * If r < 3*range, use r := r MOD range (which is either r, r - | |
160 | * range, or r - 2*range). Otherwise, iterate once more. Since | |
161 | * 3*range = 11..._2, each iteration succeeds with probability >= | |
162 | * .75. | |
163 | */ | |
164 | if (BN_cmp(r, range) >= 0) { | |
165 | if (!BN_sub(r, r, range)) | |
166 | return 0; | |
167 | if (BN_cmp(r, range) >= 0) | |
168 | if (!BN_sub(r, r, range)) | |
169 | return 0; | |
170 | } | |
171 | ||
172 | if (!--count) { | |
ddc6a5c8 | 173 | BNerr(BN_F_BNRAND_RANGE, BN_R_TOO_MANY_ITERATIONS); |
0f113f3e MC |
174 | return 0; |
175 | } | |
176 | ||
177 | } | |
178 | while (BN_cmp(r, range) >= 0); | |
179 | } else { | |
180 | do { | |
181 | /* range = 11..._2 or range = 101..._2 */ | |
ee1d4f3d | 182 | if (!bnrand(flag, r, n, BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY, ctx)) |
0f113f3e MC |
183 | return 0; |
184 | ||
185 | if (!--count) { | |
ddc6a5c8 | 186 | BNerr(BN_F_BNRAND_RANGE, BN_R_TOO_MANY_ITERATIONS); |
0f113f3e MC |
187 | return 0; |
188 | } | |
189 | } | |
190 | while (BN_cmp(r, range) >= 0); | |
191 | } | |
192 | ||
193 | bn_check_top(r); | |
194 | return 1; | |
195 | } | |
196 | ||
ee1d4f3d MC |
197 | int BN_rand_range_ex(BIGNUM *r, const BIGNUM *range, BN_CTX *ctx) |
198 | { | |
199 | return bnrand_range(NORMAL, r, range, ctx); | |
200 | } | |
201 | ||
2934be91 | 202 | #ifndef FIPS_MODE |
ddc6a5c8 RS |
203 | int BN_rand_range(BIGNUM *r, const BIGNUM *range) |
204 | { | |
ee1d4f3d MC |
205 | return bnrand_range(NORMAL, r, range, NULL); |
206 | } | |
2934be91 | 207 | #endif |
ee1d4f3d MC |
208 | |
209 | int BN_priv_rand_range_ex(BIGNUM *r, const BIGNUM *range, BN_CTX *ctx) | |
210 | { | |
211 | return bnrand_range(PRIVATE, r, range, ctx); | |
ddc6a5c8 RS |
212 | } |
213 | ||
2934be91 | 214 | #ifndef FIPS_MODE |
ddc6a5c8 RS |
215 | int BN_priv_rand_range(BIGNUM *r, const BIGNUM *range) |
216 | { | |
ee1d4f3d | 217 | return bnrand_range(PRIVATE, r, range, NULL); |
ddc6a5c8 RS |
218 | } |
219 | ||
5ecff87d | 220 | int BN_pseudo_rand(BIGNUM *rnd, int bits, int top, int bottom) |
0f113f3e | 221 | { |
5ecff87d | 222 | return BN_rand(rnd, bits, top, bottom); |
0f113f3e MC |
223 | } |
224 | ||
225 | int BN_pseudo_rand_range(BIGNUM *r, const BIGNUM *range) | |
226 | { | |
5ecff87d | 227 | return BN_rand_range(r, range); |
0f113f3e | 228 | } |
2934be91 | 229 | #endif |
8a99cb29 | 230 | |
0f113f3e MC |
231 | /* |
232 | * BN_generate_dsa_nonce generates a random number 0 <= out < range. Unlike | |
233 | * BN_rand_range, it also includes the contents of |priv| and |message| in | |
234 | * the generation so that an RNG failure isn't fatal as long as |priv| | |
235 | * remains secret. This is intended for use in DSA and ECDSA where an RNG | |
236 | * weakness leads directly to private key exposure unless this function is | |
237 | * used. | |
238 | */ | |
239 | int BN_generate_dsa_nonce(BIGNUM *out, const BIGNUM *range, | |
240 | const BIGNUM *priv, const unsigned char *message, | |
241 | size_t message_len, BN_CTX *ctx) | |
242 | { | |
9632bd0e | 243 | EVP_MD_CTX *mdctx = EVP_MD_CTX_new(); |
0f113f3e MC |
244 | /* |
245 | * We use 512 bits of random data per iteration to ensure that we have at | |
246 | * least |range| bits of randomness. | |
247 | */ | |
248 | unsigned char random_bytes[64]; | |
249 | unsigned char digest[SHA512_DIGEST_LENGTH]; | |
250 | unsigned done, todo; | |
251 | /* We generate |range|+8 bytes of random output. */ | |
252 | const unsigned num_k_bytes = BN_num_bytes(range) + 8; | |
253 | unsigned char private_bytes[96]; | |
9632bd0e | 254 | unsigned char *k_bytes = NULL; |
0f113f3e | 255 | int ret = 0; |
9632bd0e | 256 | EVP_MD *md = NULL; |
ee1d4f3d | 257 | OPENSSL_CTX *libctx = bn_get_lib_ctx(ctx); |
9632bd0e | 258 | |
ee1d4f3d | 259 | if (mdctx == NULL) |
9632bd0e | 260 | goto err; |
0f113f3e MC |
261 | |
262 | k_bytes = OPENSSL_malloc(num_k_bytes); | |
90945fa3 | 263 | if (k_bytes == NULL) |
0f113f3e MC |
264 | goto err; |
265 | ||
266 | /* We copy |priv| into a local buffer to avoid exposing its length. */ | |
267 | todo = sizeof(priv->d[0]) * priv->top; | |
268 | if (todo > sizeof(private_bytes)) { | |
269 | /* | |
270 | * No reasonable DSA or ECDSA key should have a private key this | |
271 | * large and we don't handle this case in order to avoid leaking the | |
272 | * length of the private key. | |
273 | */ | |
274 | BNerr(BN_F_BN_GENERATE_DSA_NONCE, BN_R_PRIVATE_KEY_TOO_LARGE); | |
275 | goto err; | |
276 | } | |
277 | memcpy(private_bytes, priv->d, todo); | |
278 | memset(private_bytes + todo, 0, sizeof(private_bytes) - todo); | |
279 | ||
9632bd0e MC |
280 | md = EVP_MD_fetch(libctx, "SHA512", NULL); |
281 | if (md == NULL) { | |
282 | BNerr(BN_F_BN_GENERATE_DSA_NONCE, BN_R_NO_SUITABLE_DIGEST); | |
283 | goto err; | |
284 | } | |
0f113f3e | 285 | for (done = 0; done < num_k_bytes;) { |
ee1d4f3d | 286 | if (!rand_priv_bytes_ex(libctx, random_bytes, sizeof(random_bytes))) |
9632bd0e MC |
287 | goto err; |
288 | ||
289 | if (!EVP_DigestInit_ex(mdctx, md, NULL) | |
290 | || !EVP_DigestUpdate(mdctx, &done, sizeof(done)) | |
291 | || !EVP_DigestUpdate(mdctx, private_bytes, | |
292 | sizeof(private_bytes)) | |
293 | || !EVP_DigestUpdate(mdctx, message, message_len) | |
294 | || !EVP_DigestUpdate(mdctx, random_bytes, sizeof(random_bytes)) | |
295 | || !EVP_DigestFinal_ex(mdctx, digest, NULL)) | |
0f113f3e | 296 | goto err; |
0f113f3e MC |
297 | |
298 | todo = num_k_bytes - done; | |
299 | if (todo > SHA512_DIGEST_LENGTH) | |
300 | todo = SHA512_DIGEST_LENGTH; | |
301 | memcpy(k_bytes + done, digest, todo); | |
302 | done += todo; | |
303 | } | |
304 | ||
305 | if (!BN_bin2bn(k_bytes, num_k_bytes, out)) | |
306 | goto err; | |
307 | if (BN_mod(out, out, range, ctx) != 1) | |
308 | goto err; | |
309 | ret = 1; | |
310 | ||
311 | err: | |
9632bd0e MC |
312 | EVP_MD_CTX_free(mdctx); |
313 | EVP_MD_meth_free(md); | |
b548a1f1 | 314 | OPENSSL_free(k_bytes); |
e5e71f28 | 315 | OPENSSL_cleanse(private_bytes, sizeof(private_bytes)); |
0f113f3e MC |
316 | return ret; |
317 | } |