1 | /* |
2 | * Copyright 1995-2018 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 | BN_CTX *ctx) |
25 | { |
26 | unsigned char *buf = NULL; |
27 | int b, ret = 0, bit, bytes, mask; |
28 | OPENSSL_CTX *libctx = bn_get_lib_ctx(ctx); |
29 | |
30 | if (bits == 0) { |
31 | if (top != BN_RAND_TOP_ANY || bottom != BN_RAND_BOTTOM_ANY) |
32 | goto toosmall; |
33 | BN_zero(rnd); |
34 | return 1; |
35 | } |
36 | if (bits < 0 || (bits == 1 && top > 0)) |
37 | goto toosmall; |
38 | |
39 | bytes = (bits + 7) / 8; |
40 | bit = (bits - 1) % 8; |
41 | mask = 0xff << (bit + 1); |
42 | |
43 | buf = OPENSSL_malloc(bytes); |
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 */ |
50 | b = flag == NORMAL ? rand_bytes_ex(libctx, buf, bytes) |
51 | : rand_priv_bytes_ex(libctx, buf, bytes); |
52 | if (b <= 0) |
53 | goto err; |
54 | |
55 | if (flag == TESTING) { |
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++) { |
63 | if (rand_bytes_ex(libctx, &c, 1) <= 0) |
64 | goto err; |
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 | } |
73 | |
74 | if (top >= 0) { |
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: |
93 | OPENSSL_clear_free(buf, bytes); |
94 | bn_check_top(rnd); |
95 | return ret; |
96 | |
97 | toosmall: |
98 | BNerr(BN_F_BNRAND, BN_R_BITS_TOO_SMALL); |
99 | return 0; |
100 | } |
101 | |
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 | } |
106 | #ifndef FIPS_MODE |
107 | int BN_rand(BIGNUM *rnd, int bits, int top, int bottom) |
108 | { |
109 | return bnrand(NORMAL, rnd, bits, top, bottom, NULL); |
110 | } |
111 | |
112 | int BN_bntest_rand(BIGNUM *rnd, int bits, int top, int bottom) |
113 | { |
114 | return bnrand(TESTING, rnd, bits, top, bottom, NULL); |
115 | } |
116 | #endif |
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); |
121 | } |
122 | |
123 | #ifndef FIPS_MODE |
124 | int BN_priv_rand(BIGNUM *rnd, int bits, int top, int bottom) |
125 | { |
126 | return bnrand(PRIVATE, rnd, bits, top, bottom, NULL); |
127 | } |
128 | #endif |
129 | |
130 | /* random number r: 0 <= r < range */ |
131 | static int bnrand_range(BNRAND_FLAG flag, BIGNUM *r, const BIGNUM *range, |
132 | BN_CTX *ctx) |
133 | { |
134 | int n; |
135 | int count = 100; |
136 | |
137 | if (range->neg || BN_is_zero(range)) { |
138 | BNerr(BN_F_BNRAND_RANGE, BN_R_INVALID_RANGE); |
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 { |
154 | if (!bnrand(flag, r, n + 1, BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY, |
155 | ctx)) |
156 | return 0; |
157 | |
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) { |
173 | BNerr(BN_F_BNRAND_RANGE, BN_R_TOO_MANY_ITERATIONS); |
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 */ |
182 | if (!bnrand(flag, r, n, BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY, ctx)) |
183 | return 0; |
184 | |
185 | if (!--count) { |
186 | BNerr(BN_F_BNRAND_RANGE, BN_R_TOO_MANY_ITERATIONS); |
187 | return 0; |
188 | } |
189 | } |
190 | while (BN_cmp(r, range) >= 0); |
191 | } |
192 | |
193 | bn_check_top(r); |
194 | return 1; |
195 | } |
196 | |
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 | |
202 | #ifndef FIPS_MODE |
203 | int BN_rand_range(BIGNUM *r, const BIGNUM *range) |
204 | { |
205 | return bnrand_range(NORMAL, r, range, NULL); |
206 | } |
207 | #endif |
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); |
212 | } |
213 | |
214 | #ifndef FIPS_MODE |
215 | int BN_priv_rand_range(BIGNUM *r, const BIGNUM *range) |
216 | { |
217 | return bnrand_range(PRIVATE, r, range, NULL); |
218 | } |
219 | |
220 | int BN_pseudo_rand(BIGNUM *rnd, int bits, int top, int bottom) |
221 | { |
222 | return BN_rand(rnd, bits, top, bottom); |
223 | } |
224 | |
225 | int BN_pseudo_rand_range(BIGNUM *r, const BIGNUM *range) |
226 | { |
227 | return BN_rand_range(r, range); |
228 | } |
229 | #endif |
230 | |
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 | { |
243 | EVP_MD_CTX *mdctx = EVP_MD_CTX_new(); |
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]; |
254 | unsigned char *k_bytes = NULL; |
255 | int ret = 0; |
256 | EVP_MD *md = NULL; |
257 | OPENSSL_CTX *libctx = bn_get_lib_ctx(ctx); |
258 | |
259 | if (mdctx == NULL) |
260 | goto err; |
261 | |
262 | k_bytes = OPENSSL_malloc(num_k_bytes); |
263 | if (k_bytes == NULL) |
264 | goto err; |
265 | |
266 | /* We copy |priv| into a local buffer to avoid exposing its length. */ |
267 | if (BN_bn2binpad(priv, private_bytes, sizeof(private_bytes)) < 0) { |
268 | /* |
269 | * No reasonable DSA or ECDSA key should have a private key this |
270 | * large and we don't handle this case in order to avoid leaking the |
271 | * length of the private key. |
272 | */ |
273 | BNerr(BN_F_BN_GENERATE_DSA_NONCE, BN_R_PRIVATE_KEY_TOO_LARGE); |
274 | goto err; |
275 | } |
276 | |
277 | md = EVP_MD_fetch(libctx, "SHA512" , NULL); |
278 | if (md == NULL) { |
279 | BNerr(BN_F_BN_GENERATE_DSA_NONCE, BN_R_NO_SUITABLE_DIGEST); |
280 | goto err; |
281 | } |
282 | for (done = 0; done < num_k_bytes;) { |
283 | if (!rand_priv_bytes_ex(libctx, random_bytes, sizeof(random_bytes))) |
284 | goto err; |
285 | |
286 | if (!EVP_DigestInit_ex(mdctx, md, NULL) |
287 | || !EVP_DigestUpdate(mdctx, &done, sizeof(done)) |
288 | || !EVP_DigestUpdate(mdctx, private_bytes, |
289 | sizeof(private_bytes)) |
290 | || !EVP_DigestUpdate(mdctx, message, message_len) |
291 | || !EVP_DigestUpdate(mdctx, random_bytes, sizeof(random_bytes)) |
292 | || !EVP_DigestFinal_ex(mdctx, digest, NULL)) |
293 | goto err; |
294 | |
295 | todo = num_k_bytes - done; |
296 | if (todo > SHA512_DIGEST_LENGTH) |
297 | todo = SHA512_DIGEST_LENGTH; |
298 | memcpy(k_bytes + done, digest, todo); |
299 | done += todo; |
300 | } |
301 | |
302 | if (!BN_bin2bn(k_bytes, num_k_bytes, out)) |
303 | goto err; |
304 | if (BN_mod(out, out, range, ctx) != 1) |
305 | goto err; |
306 | ret = 1; |
307 | |
308 | err: |
309 | EVP_MD_CTX_free(mdctx); |
310 | EVP_MD_free(md); |
311 | OPENSSL_free(k_bytes); |
312 | OPENSSL_cleanse(private_bytes, sizeof(private_bytes)); |
313 | return ret; |
314 | } |
315 | |