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