]>
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 | } | |
0f113f3e MC |
106 | int BN_rand(BIGNUM *rnd, int bits, int top, int bottom) |
107 | { | |
ee1d4f3d | 108 | return bnrand(NORMAL, rnd, bits, top, bottom, NULL); |
0f113f3e MC |
109 | } |
110 | ||
0f113f3e MC |
111 | int BN_bntest_rand(BIGNUM *rnd, int bits, int top, int bottom) |
112 | { | |
ee1d4f3d MC |
113 | return bnrand(TESTING, rnd, bits, top, bottom, NULL); |
114 | } | |
115 | ||
116 | int BN_priv_rand_ex(BIGNUM *rnd, int bits, int top, int bottom, BN_CTX *ctx) | |
117 | { | |
118 | return bnrand(PRIVATE, rnd, bits, top, bottom, ctx); | |
ddc6a5c8 RS |
119 | } |
120 | ||
121 | int BN_priv_rand(BIGNUM *rnd, int bits, int top, int bottom) | |
122 | { | |
ee1d4f3d | 123 | return bnrand(PRIVATE, rnd, bits, top, bottom, NULL); |
0f113f3e | 124 | } |
57e7d3ce | 125 | |
e3068929 | 126 | /* random number r: 0 <= r < range */ |
ee1d4f3d MC |
127 | static int bnrand_range(BNRAND_FLAG flag, BIGNUM *r, const BIGNUM *range, |
128 | BN_CTX *ctx) | |
0f113f3e | 129 | { |
3bc0ab06 | 130 | int n; |
0f113f3e MC |
131 | int count = 100; |
132 | ||
133 | if (range->neg || BN_is_zero(range)) { | |
ddc6a5c8 | 134 | BNerr(BN_F_BNRAND_RANGE, BN_R_INVALID_RANGE); |
0f113f3e MC |
135 | return 0; |
136 | } | |
137 | ||
138 | n = BN_num_bits(range); /* n > 0 */ | |
139 | ||
140 | /* BN_is_bit_set(range, n - 1) always holds */ | |
141 | ||
142 | if (n == 1) | |
143 | BN_zero(r); | |
144 | else if (!BN_is_bit_set(range, n - 2) && !BN_is_bit_set(range, n - 3)) { | |
145 | /* | |
146 | * range = 100..._2, so 3*range (= 11..._2) is exactly one bit longer | |
147 | * than range | |
148 | */ | |
149 | do { | |
ee1d4f3d MC |
150 | if (!bnrand(flag, r, n + 1, BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY, |
151 | ctx)) | |
0f113f3e | 152 | return 0; |
3bc0ab06 | 153 | |
0f113f3e MC |
154 | /* |
155 | * If r < 3*range, use r := r MOD range (which is either r, r - | |
156 | * range, or r - 2*range). Otherwise, iterate once more. Since | |
157 | * 3*range = 11..._2, each iteration succeeds with probability >= | |
158 | * .75. | |
159 | */ | |
160 | if (BN_cmp(r, range) >= 0) { | |
161 | if (!BN_sub(r, r, range)) | |
162 | return 0; | |
163 | if (BN_cmp(r, range) >= 0) | |
164 | if (!BN_sub(r, r, range)) | |
165 | return 0; | |
166 | } | |
167 | ||
168 | if (!--count) { | |
ddc6a5c8 | 169 | BNerr(BN_F_BNRAND_RANGE, BN_R_TOO_MANY_ITERATIONS); |
0f113f3e MC |
170 | return 0; |
171 | } | |
172 | ||
173 | } | |
174 | while (BN_cmp(r, range) >= 0); | |
175 | } else { | |
176 | do { | |
177 | /* range = 11..._2 or range = 101..._2 */ | |
ee1d4f3d | 178 | if (!bnrand(flag, r, n, BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY, ctx)) |
0f113f3e MC |
179 | return 0; |
180 | ||
181 | if (!--count) { | |
ddc6a5c8 | 182 | BNerr(BN_F_BNRAND_RANGE, BN_R_TOO_MANY_ITERATIONS); |
0f113f3e MC |
183 | return 0; |
184 | } | |
185 | } | |
186 | while (BN_cmp(r, range) >= 0); | |
187 | } | |
188 | ||
189 | bn_check_top(r); | |
190 | return 1; | |
191 | } | |
192 | ||
ee1d4f3d MC |
193 | int BN_rand_range_ex(BIGNUM *r, const BIGNUM *range, BN_CTX *ctx) |
194 | { | |
195 | return bnrand_range(NORMAL, r, range, ctx); | |
196 | } | |
197 | ||
ddc6a5c8 RS |
198 | int BN_rand_range(BIGNUM *r, const BIGNUM *range) |
199 | { | |
ee1d4f3d MC |
200 | return bnrand_range(NORMAL, r, range, NULL); |
201 | } | |
202 | ||
203 | int BN_priv_rand_range_ex(BIGNUM *r, const BIGNUM *range, BN_CTX *ctx) | |
204 | { | |
205 | return bnrand_range(PRIVATE, r, range, ctx); | |
ddc6a5c8 RS |
206 | } |
207 | ||
208 | int BN_priv_rand_range(BIGNUM *r, const BIGNUM *range) | |
209 | { | |
ee1d4f3d | 210 | return bnrand_range(PRIVATE, r, range, NULL); |
ddc6a5c8 RS |
211 | } |
212 | ||
5ecff87d | 213 | int BN_pseudo_rand(BIGNUM *rnd, int bits, int top, int bottom) |
0f113f3e | 214 | { |
5ecff87d | 215 | return BN_rand(rnd, bits, top, bottom); |
0f113f3e MC |
216 | } |
217 | ||
218 | int BN_pseudo_rand_range(BIGNUM *r, const BIGNUM *range) | |
219 | { | |
5ecff87d | 220 | return BN_rand_range(r, range); |
0f113f3e | 221 | } |
8a99cb29 | 222 | |
0f113f3e MC |
223 | /* |
224 | * BN_generate_dsa_nonce generates a random number 0 <= out < range. Unlike | |
225 | * BN_rand_range, it also includes the contents of |priv| and |message| in | |
226 | * the generation so that an RNG failure isn't fatal as long as |priv| | |
227 | * remains secret. This is intended for use in DSA and ECDSA where an RNG | |
228 | * weakness leads directly to private key exposure unless this function is | |
229 | * used. | |
230 | */ | |
231 | int BN_generate_dsa_nonce(BIGNUM *out, const BIGNUM *range, | |
232 | const BIGNUM *priv, const unsigned char *message, | |
233 | size_t message_len, BN_CTX *ctx) | |
234 | { | |
9632bd0e | 235 | EVP_MD_CTX *mdctx = EVP_MD_CTX_new(); |
0f113f3e MC |
236 | /* |
237 | * We use 512 bits of random data per iteration to ensure that we have at | |
238 | * least |range| bits of randomness. | |
239 | */ | |
240 | unsigned char random_bytes[64]; | |
241 | unsigned char digest[SHA512_DIGEST_LENGTH]; | |
242 | unsigned done, todo; | |
243 | /* We generate |range|+8 bytes of random output. */ | |
244 | const unsigned num_k_bytes = BN_num_bytes(range) + 8; | |
245 | unsigned char private_bytes[96]; | |
9632bd0e | 246 | unsigned char *k_bytes = NULL; |
0f113f3e | 247 | int ret = 0; |
9632bd0e | 248 | EVP_MD *md = NULL; |
ee1d4f3d | 249 | OPENSSL_CTX *libctx = bn_get_lib_ctx(ctx); |
9632bd0e | 250 | |
ee1d4f3d | 251 | if (mdctx == NULL) |
9632bd0e | 252 | goto err; |
0f113f3e MC |
253 | |
254 | k_bytes = OPENSSL_malloc(num_k_bytes); | |
90945fa3 | 255 | if (k_bytes == NULL) |
0f113f3e MC |
256 | goto err; |
257 | ||
258 | /* We copy |priv| into a local buffer to avoid exposing its length. */ | |
259 | todo = sizeof(priv->d[0]) * priv->top; | |
260 | if (todo > sizeof(private_bytes)) { | |
261 | /* | |
262 | * No reasonable DSA or ECDSA key should have a private key this | |
263 | * large and we don't handle this case in order to avoid leaking the | |
264 | * length of the private key. | |
265 | */ | |
266 | BNerr(BN_F_BN_GENERATE_DSA_NONCE, BN_R_PRIVATE_KEY_TOO_LARGE); | |
267 | goto err; | |
268 | } | |
269 | memcpy(private_bytes, priv->d, todo); | |
270 | memset(private_bytes + todo, 0, sizeof(private_bytes) - todo); | |
271 | ||
9632bd0e MC |
272 | md = EVP_MD_fetch(libctx, "SHA512", NULL); |
273 | if (md == NULL) { | |
274 | BNerr(BN_F_BN_GENERATE_DSA_NONCE, BN_R_NO_SUITABLE_DIGEST); | |
275 | goto err; | |
276 | } | |
0f113f3e | 277 | for (done = 0; done < num_k_bytes;) { |
ee1d4f3d | 278 | if (!rand_priv_bytes_ex(libctx, random_bytes, sizeof(random_bytes))) |
9632bd0e MC |
279 | goto err; |
280 | ||
281 | if (!EVP_DigestInit_ex(mdctx, md, NULL) | |
282 | || !EVP_DigestUpdate(mdctx, &done, sizeof(done)) | |
283 | || !EVP_DigestUpdate(mdctx, private_bytes, | |
284 | sizeof(private_bytes)) | |
285 | || !EVP_DigestUpdate(mdctx, message, message_len) | |
286 | || !EVP_DigestUpdate(mdctx, random_bytes, sizeof(random_bytes)) | |
287 | || !EVP_DigestFinal_ex(mdctx, digest, NULL)) | |
0f113f3e | 288 | goto err; |
0f113f3e MC |
289 | |
290 | todo = num_k_bytes - done; | |
291 | if (todo > SHA512_DIGEST_LENGTH) | |
292 | todo = SHA512_DIGEST_LENGTH; | |
293 | memcpy(k_bytes + done, digest, todo); | |
294 | done += todo; | |
295 | } | |
296 | ||
297 | if (!BN_bin2bn(k_bytes, num_k_bytes, out)) | |
298 | goto err; | |
299 | if (BN_mod(out, out, range, ctx) != 1) | |
300 | goto err; | |
301 | ret = 1; | |
302 | ||
303 | err: | |
9632bd0e MC |
304 | EVP_MD_CTX_free(mdctx); |
305 | EVP_MD_meth_free(md); | |
b548a1f1 | 306 | OPENSSL_free(k_bytes); |
e5e71f28 | 307 | OPENSSL_cleanse(private_bytes, sizeof(private_bytes)); |
0f113f3e MC |
308 | return ret; |
309 | } |