]>
Commit | Line | Data |
---|---|---|
4f22f405 RS |
1 | /* |
2 | * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved. | |
983495c4 | 3 | * |
4f22f405 RS |
4 | * Licensed under the OpenSSL license (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 | |
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> |
8a99cb29 | 15 | #include <openssl/sha.h> |
d02b48c6 | 16 | |
38e33cef | 17 | static int bnrand(int pseudorand, BIGNUM *rnd, int bits, int top, int bottom) |
0f113f3e MC |
18 | { |
19 | unsigned char *buf = NULL; | |
20 | int ret = 0, bit, bytes, mask; | |
21 | time_t tim; | |
22 | ||
efee575a MC |
23 | if (bits < 0 || (bits == 1 && top > 0)) { |
24 | BNerr(BN_F_BNRAND, BN_R_BITS_TOO_SMALL); | |
25 | return 0; | |
26 | } | |
27 | ||
0f113f3e MC |
28 | if (bits == 0) { |
29 | BN_zero(rnd); | |
30 | return 1; | |
31 | } | |
32 | ||
33 | bytes = (bits + 7) / 8; | |
34 | bit = (bits - 1) % 8; | |
35 | mask = 0xff << (bit + 1); | |
36 | ||
b196e7d9 | 37 | buf = OPENSSL_malloc(bytes); |
0f113f3e MC |
38 | if (buf == NULL) { |
39 | BNerr(BN_F_BNRAND, ERR_R_MALLOC_FAILURE); | |
40 | goto err; | |
41 | } | |
42 | ||
43 | /* make a random number and set the top and bottom bits */ | |
44 | time(&tim); | |
45 | RAND_add(&tim, sizeof(tim), 0.0); | |
46 | ||
47 | if (pseudorand) { | |
266483d2 | 48 | if (RAND_bytes(buf, bytes) <= 0) |
0f113f3e MC |
49 | goto err; |
50 | } else { | |
51 | if (RAND_bytes(buf, bytes) <= 0) | |
52 | goto err; | |
53 | } | |
38e33cef | 54 | |
0f113f3e MC |
55 | if (pseudorand == 2) { |
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++) { | |
266483d2 MC |
63 | if (RAND_bytes(&c, 1) <= 0) |
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 MC |
94 | bn_check_top(rnd); |
95 | return (ret); | |
96 | } | |
97 | ||
98 | int BN_rand(BIGNUM *rnd, int bits, int top, int bottom) | |
99 | { | |
100 | return bnrand(0, rnd, bits, top, bottom); | |
101 | } | |
102 | ||
103 | int BN_pseudo_rand(BIGNUM *rnd, int bits, int top, int bottom) | |
104 | { | |
105 | return bnrand(1, rnd, bits, top, bottom); | |
106 | } | |
111482cf | 107 | |
0f113f3e MC |
108 | int BN_bntest_rand(BIGNUM *rnd, int bits, int top, int bottom) |
109 | { | |
110 | return bnrand(2, rnd, bits, top, bottom); | |
111 | } | |
57e7d3ce | 112 | |
e3068929 | 113 | /* random number r: 0 <= r < range */ |
0d6f9c71 | 114 | static int bn_rand_range(int pseudo, BIGNUM *r, const BIGNUM *range) |
0f113f3e MC |
115 | { |
116 | int (*bn_rand) (BIGNUM *, int, int, int) = | |
117 | pseudo ? BN_pseudo_rand : BN_rand; | |
118 | int n; | |
119 | int count = 100; | |
120 | ||
121 | if (range->neg || BN_is_zero(range)) { | |
122 | BNerr(BN_F_BN_RAND_RANGE, BN_R_INVALID_RANGE); | |
123 | return 0; | |
124 | } | |
125 | ||
126 | n = BN_num_bits(range); /* n > 0 */ | |
127 | ||
128 | /* BN_is_bit_set(range, n - 1) always holds */ | |
129 | ||
130 | if (n == 1) | |
131 | BN_zero(r); | |
132 | else if (!BN_is_bit_set(range, n - 2) && !BN_is_bit_set(range, n - 3)) { | |
133 | /* | |
134 | * range = 100..._2, so 3*range (= 11..._2) is exactly one bit longer | |
135 | * than range | |
136 | */ | |
137 | do { | |
138 | if (!bn_rand(r, n + 1, -1, 0)) | |
139 | return 0; | |
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) { | |
155 | BNerr(BN_F_BN_RAND_RANGE, BN_R_TOO_MANY_ITERATIONS); | |
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 */ | |
164 | if (!bn_rand(r, n, -1, 0)) | |
165 | return 0; | |
166 | ||
167 | if (!--count) { | |
168 | BNerr(BN_F_BN_RAND_RANGE, BN_R_TOO_MANY_ITERATIONS); | |
169 | return 0; | |
170 | } | |
171 | } | |
172 | while (BN_cmp(r, range) >= 0); | |
173 | } | |
174 | ||
175 | bn_check_top(r); | |
176 | return 1; | |
177 | } | |
178 | ||
179 | int BN_rand_range(BIGNUM *r, const BIGNUM *range) | |
180 | { | |
181 | return bn_rand_range(0, r, range); | |
182 | } | |
183 | ||
184 | int BN_pseudo_rand_range(BIGNUM *r, const BIGNUM *range) | |
185 | { | |
186 | return bn_rand_range(1, r, range); | |
187 | } | |
8a99cb29 | 188 | |
0f113f3e MC |
189 | /* |
190 | * BN_generate_dsa_nonce generates a random number 0 <= out < range. Unlike | |
191 | * BN_rand_range, it also includes the contents of |priv| and |message| in | |
192 | * the generation so that an RNG failure isn't fatal as long as |priv| | |
193 | * remains secret. This is intended for use in DSA and ECDSA where an RNG | |
194 | * weakness leads directly to private key exposure unless this function is | |
195 | * used. | |
196 | */ | |
197 | int BN_generate_dsa_nonce(BIGNUM *out, const BIGNUM *range, | |
198 | const BIGNUM *priv, const unsigned char *message, | |
199 | size_t message_len, BN_CTX *ctx) | |
200 | { | |
201 | SHA512_CTX sha; | |
202 | /* | |
203 | * We use 512 bits of random data per iteration to ensure that we have at | |
204 | * least |range| bits of randomness. | |
205 | */ | |
206 | unsigned char random_bytes[64]; | |
207 | unsigned char digest[SHA512_DIGEST_LENGTH]; | |
208 | unsigned done, todo; | |
209 | /* We generate |range|+8 bytes of random output. */ | |
210 | const unsigned num_k_bytes = BN_num_bytes(range) + 8; | |
211 | unsigned char private_bytes[96]; | |
212 | unsigned char *k_bytes; | |
213 | int ret = 0; | |
214 | ||
215 | k_bytes = OPENSSL_malloc(num_k_bytes); | |
90945fa3 | 216 | if (k_bytes == NULL) |
0f113f3e MC |
217 | goto err; |
218 | ||
219 | /* We copy |priv| into a local buffer to avoid exposing its length. */ | |
220 | todo = sizeof(priv->d[0]) * priv->top; | |
221 | if (todo > sizeof(private_bytes)) { | |
222 | /* | |
223 | * No reasonable DSA or ECDSA key should have a private key this | |
224 | * large and we don't handle this case in order to avoid leaking the | |
225 | * length of the private key. | |
226 | */ | |
227 | BNerr(BN_F_BN_GENERATE_DSA_NONCE, BN_R_PRIVATE_KEY_TOO_LARGE); | |
228 | goto err; | |
229 | } | |
230 | memcpy(private_bytes, priv->d, todo); | |
231 | memset(private_bytes + todo, 0, sizeof(private_bytes) - todo); | |
232 | ||
233 | for (done = 0; done < num_k_bytes;) { | |
234 | if (RAND_bytes(random_bytes, sizeof(random_bytes)) != 1) | |
235 | goto err; | |
236 | SHA512_Init(&sha); | |
237 | SHA512_Update(&sha, &done, sizeof(done)); | |
238 | SHA512_Update(&sha, private_bytes, sizeof(private_bytes)); | |
239 | SHA512_Update(&sha, message, message_len); | |
240 | SHA512_Update(&sha, random_bytes, sizeof(random_bytes)); | |
241 | SHA512_Final(digest, &sha); | |
242 | ||
243 | todo = num_k_bytes - done; | |
244 | if (todo > SHA512_DIGEST_LENGTH) | |
245 | todo = SHA512_DIGEST_LENGTH; | |
246 | memcpy(k_bytes + done, digest, todo); | |
247 | done += todo; | |
248 | } | |
249 | ||
250 | if (!BN_bin2bn(k_bytes, num_k_bytes, out)) | |
251 | goto err; | |
252 | if (BN_mod(out, out, range, ctx) != 1) | |
253 | goto err; | |
254 | ret = 1; | |
255 | ||
256 | err: | |
b548a1f1 | 257 | OPENSSL_free(k_bytes); |
0f113f3e MC |
258 | return ret; |
259 | } |