Branch data Line data Source code
1 : : /* crypto/bn/bn_rand.c */
2 : : /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
3 : : * All rights reserved.
4 : : *
5 : : * This package is an SSL implementation written
6 : : * by Eric Young (eay@cryptsoft.com).
7 : : * The implementation was written so as to conform with Netscapes SSL.
8 : : *
9 : : * This library is free for commercial and non-commercial use as long as
10 : : * the following conditions are aheared to. The following conditions
11 : : * apply to all code found in this distribution, be it the RC4, RSA,
12 : : * lhash, DES, etc., code; not just the SSL code. The SSL documentation
13 : : * included with this distribution is covered by the same copyright terms
14 : : * except that the holder is Tim Hudson (tjh@cryptsoft.com).
15 : : *
16 : : * Copyright remains Eric Young's, and as such any Copyright notices in
17 : : * the code are not to be removed.
18 : : * If this package is used in a product, Eric Young should be given attribution
19 : : * as the author of the parts of the library used.
20 : : * This can be in the form of a textual message at program startup or
21 : : * in documentation (online or textual) provided with the package.
22 : : *
23 : : * Redistribution and use in source and binary forms, with or without
24 : : * modification, are permitted provided that the following conditions
25 : : * are met:
26 : : * 1. Redistributions of source code must retain the copyright
27 : : * notice, this list of conditions and the following disclaimer.
28 : : * 2. Redistributions in binary form must reproduce the above copyright
29 : : * notice, this list of conditions and the following disclaimer in the
30 : : * documentation and/or other materials provided with the distribution.
31 : : * 3. All advertising materials mentioning features or use of this software
32 : : * must display the following acknowledgement:
33 : : * "This product includes cryptographic software written by
34 : : * Eric Young (eay@cryptsoft.com)"
35 : : * The word 'cryptographic' can be left out if the rouines from the library
36 : : * being used are not cryptographic related :-).
37 : : * 4. If you include any Windows specific code (or a derivative thereof) from
38 : : * the apps directory (application code) you must include an acknowledgement:
39 : : * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
40 : : *
41 : : * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
42 : : * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
43 : : * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
44 : : * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
45 : : * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
46 : : * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
47 : : * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
48 : : * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
49 : : * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
50 : : * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
51 : : * SUCH DAMAGE.
52 : : *
53 : : * The licence and distribution terms for any publically available version or
54 : : * derivative of this code cannot be changed. i.e. this code cannot simply be
55 : : * copied and put under another distribution licence
56 : : * [including the GNU Public Licence.]
57 : : */
58 : : /* ====================================================================
59 : : * Copyright (c) 1998-2001 The OpenSSL Project. All rights reserved.
60 : : *
61 : : * Redistribution and use in source and binary forms, with or without
62 : : * modification, are permitted provided that the following conditions
63 : : * are met:
64 : : *
65 : : * 1. Redistributions of source code must retain the above copyright
66 : : * notice, this list of conditions and the following disclaimer.
67 : : *
68 : : * 2. Redistributions in binary form must reproduce the above copyright
69 : : * notice, this list of conditions and the following disclaimer in
70 : : * the documentation and/or other materials provided with the
71 : : * distribution.
72 : : *
73 : : * 3. All advertising materials mentioning features or use of this
74 : : * software must display the following acknowledgment:
75 : : * "This product includes software developed by the OpenSSL Project
76 : : * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
77 : : *
78 : : * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
79 : : * endorse or promote products derived from this software without
80 : : * prior written permission. For written permission, please contact
81 : : * openssl-core@openssl.org.
82 : : *
83 : : * 5. Products derived from this software may not be called "OpenSSL"
84 : : * nor may "OpenSSL" appear in their names without prior written
85 : : * permission of the OpenSSL Project.
86 : : *
87 : : * 6. Redistributions of any form whatsoever must retain the following
88 : : * acknowledgment:
89 : : * "This product includes software developed by the OpenSSL Project
90 : : * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
91 : : *
92 : : * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
93 : : * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
94 : : * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
95 : : * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
96 : : * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
97 : : * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
98 : : * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
99 : : * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
100 : : * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
101 : : * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
102 : : * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
103 : : * OF THE POSSIBILITY OF SUCH DAMAGE.
104 : : * ====================================================================
105 : : *
106 : : * This product includes cryptographic software written by Eric Young
107 : : * (eay@cryptsoft.com). This product includes software written by Tim
108 : : * Hudson (tjh@cryptsoft.com).
109 : : *
110 : : */
111 : :
112 : : #define OPENSSL_FIPSAPI
113 : :
114 : : #include <stdio.h>
115 : : #include <time.h>
116 : : #include "cryptlib.h"
117 : : #include "bn_lcl.h"
118 : : #include <openssl/rand.h>
119 : : #include <openssl/sha.h>
120 : :
121 : 41127 : static int bnrand(int pseudorand, BIGNUM *rnd, int bits, int top, int bottom)
122 : : {
123 : 41127 : unsigned char *buf=NULL;
124 : 41127 : int ret=0,bit,bytes,mask;
125 : : time_t tim;
126 : :
127 [ - + ]: 41127 : if (bits == 0)
128 : : {
129 : 0 : BN_zero(rnd);
130 : 0 : return 1;
131 : : }
132 : :
133 : 41127 : bytes=(bits+7)/8;
134 : 41127 : bit=(bits-1)%8;
135 : 41127 : mask=0xff<<(bit+1);
136 : :
137 : 41127 : buf=(unsigned char *)OPENSSL_malloc(bytes);
138 [ - + ]: 41127 : if (buf == NULL)
139 : : {
140 : 0 : BNerr(BN_F_BNRAND,ERR_R_MALLOC_FAILURE);
141 : 0 : goto err;
142 : : }
143 : :
144 : : /* make a random number and set the top and bottom bits */
145 : 41127 : time(&tim);
146 : 41127 : RAND_add(&tim,sizeof(tim),0.0);
147 : :
148 [ + + ]: 41127 : if (pseudorand)
149 : : {
150 [ + - ]: 6273 : if (RAND_pseudo_bytes(buf, bytes) == -1)
151 : : goto err;
152 : : }
153 : : else
154 : : {
155 [ + - ]: 34854 : if (RAND_bytes(buf, bytes) <= 0)
156 : : goto err;
157 : : }
158 : :
159 : : #if 1
160 [ + + ]: 41127 : if (pseudorand == 2)
161 : : {
162 : : /* generate patterns that are more likely to trigger BN
163 : : library bugs */
164 : : int i;
165 : : unsigned char c;
166 : :
167 [ + + ]: 257511 : for (i = 0; i < bytes; i++)
168 : : {
169 : 254146 : RAND_pseudo_bytes(&c, 1);
170 [ + + ][ + + ]: 254146 : if (c >= 128 && i > 0)
171 : 125506 : buf[i] = buf[i-1];
172 [ + + ]: 128640 : else if (c < 42)
173 : 41669 : buf[i] = 0;
174 [ + + ]: 86971 : else if (c < 84)
175 : 41525 : buf[i] = 255;
176 : : }
177 : : }
178 : : #endif
179 : :
180 [ + + ]: 41127 : if (top != -1)
181 : : {
182 [ + + ]: 19692 : if (top)
183 : : {
184 [ - + ]: 1095 : if (bit == 0)
185 : : {
186 : 0 : buf[0]=1;
187 : 0 : buf[1]|=0x80;
188 : : }
189 : : else
190 : : {
191 : 1095 : buf[0]|=(3<<(bit-1));
192 : : }
193 : : }
194 : : else
195 : : {
196 : 18597 : buf[0]|=(1<<bit);
197 : : }
198 : : }
199 : 41127 : buf[0] &= ~mask;
200 [ + + ]: 41127 : if (bottom) /* set bottom bit if requested */
201 : 15165 : buf[bytes-1]|=1;
202 [ + - ]: 41127 : if (!BN_bin2bn(buf,bytes,rnd)) goto err;
203 : 41127 : ret=1;
204 : : err:
205 [ + - ]: 41127 : if (buf != NULL)
206 : : {
207 : 41127 : OPENSSL_cleanse(buf,bytes);
208 : 41127 : OPENSSL_free(buf);
209 : : }
210 : : bn_check_top(rnd);
211 : 41127 : return(ret);
212 : : }
213 : :
214 : 34854 : int BN_rand(BIGNUM *rnd, int bits, int top, int bottom)
215 : : {
216 : 34854 : return bnrand(0, rnd, bits, top, bottom);
217 : : }
218 : :
219 : 2908 : int BN_pseudo_rand(BIGNUM *rnd, int bits, int top, int bottom)
220 : : {
221 : 2908 : return bnrand(1, rnd, bits, top, bottom);
222 : : }
223 : :
224 : : #if 1
225 : 3365 : int BN_bntest_rand(BIGNUM *rnd, int bits, int top, int bottom)
226 : : {
227 : 3365 : return bnrand(2, rnd, bits, top, bottom);
228 : : }
229 : : #endif
230 : :
231 : :
232 : : /* random number r: 0 <= r < range */
233 : 19086 : static int bn_rand_range(int pseudo, BIGNUM *r, const BIGNUM *range)
234 : : {
235 [ + + ]: 19086 : int (*bn_rand)(BIGNUM *, int, int, int) = pseudo ? BN_pseudo_rand : BN_rand;
236 : : int n;
237 : 19086 : int count = 100;
238 : :
239 [ + - ][ - + ]: 19086 : if (range->neg || BN_is_zero(range))
240 : : {
241 : 0 : BNerr(BN_F_BN_RAND_RANGE, BN_R_INVALID_RANGE);
242 : 0 : return 0;
243 : : }
244 : :
245 : 19086 : n = BN_num_bits(range); /* n > 0 */
246 : :
247 : : /* BN_is_bit_set(range, n - 1) always holds */
248 : :
249 [ - + ]: 19086 : if (n == 1)
250 : 0 : BN_zero(r);
251 : : #ifdef OPENSSL_FIPS
252 : : /* FIPS 186-3 is picky about how random numbers for keys etc are
253 : : * generated. So we just use the second case which is equivalent to
254 : : * "Generation by Testing Candidates" mentioned in B.1.2 et al.
255 : : */
256 : : else if (!FIPS_module_mode() && !BN_is_bit_set(range, n - 2) && !BN_is_bit_set(range, n - 3))
257 : : #else
258 [ + + ][ + + ]: 19086 : else if (!BN_is_bit_set(range, n - 2) && !BN_is_bit_set(range, n - 3))
259 : : #endif
260 : : {
261 : : /* range = 100..._2,
262 : : * so 3*range (= 11..._2) is exactly one bit longer than range */
263 : : do
264 : : {
265 [ + - ]: 2520 : if (!bn_rand(r, n + 1, -1, 0)) return 0;
266 : : /* If r < 3*range, use r := r MOD range
267 : : * (which is either r, r - range, or r - 2*range).
268 : : * Otherwise, iterate once more.
269 : : * Since 3*range = 11..._2, each iteration succeeds with
270 : : * probability >= .75. */
271 [ + + ]: 2520 : if (BN_cmp(r ,range) >= 0)
272 : : {
273 [ + - ]: 1868 : if (!BN_sub(r, r, range)) return 0;
274 [ + + ]: 1868 : if (BN_cmp(r, range) >= 0)
275 [ + - ]: 1244 : if (!BN_sub(r, r, range)) return 0;
276 : : }
277 : :
278 [ - + ]: 2520 : if (!--count)
279 : : {
280 : 0 : BNerr(BN_F_BN_RAND_RANGE, BN_R_TOO_MANY_ITERATIONS);
281 : 0 : return 0;
282 : : }
283 : :
284 : : }
285 [ + + ]: 19715 : while (BN_cmp(r, range) >= 0);
286 : : }
287 : : else
288 : : {
289 : : do
290 : : {
291 : : /* range = 11..._2 or range = 101..._2 */
292 [ + - ]: 18713 : if (!bn_rand(r, n, -1, 0)) return 0;
293 : :
294 [ - + ]: 18713 : if (!--count)
295 : : {
296 : 0 : BNerr(BN_F_BN_RAND_RANGE, BN_R_TOO_MANY_ITERATIONS);
297 : 0 : return 0;
298 : : }
299 : : }
300 [ + + ]: 18713 : while (BN_cmp(r, range) >= 0);
301 : : }
302 : :
303 : : bn_check_top(r);
304 : : return 1;
305 : : }
306 : :
307 : :
308 : 16577 : int BN_rand_range(BIGNUM *r, const BIGNUM *range)
309 : : {
310 : 16577 : return bn_rand_range(0, r, range);
311 : : }
312 : :
313 : 2509 : int BN_pseudo_rand_range(BIGNUM *r, const BIGNUM *range)
314 : : {
315 : 2509 : return bn_rand_range(1, r, range);
316 : : }
317 : :
318 : : #ifndef OPENSSL_NO_SHA512
319 : : /* BN_generate_dsa_nonce generates a random number 0 <= out < range. Unlike
320 : : * BN_rand_range, it also includes the contents of |priv| and |message| in the
321 : : * generation so that an RNG failure isn't fatal as long as |priv| remains
322 : : * secret. This is intended for use in DSA and ECDSA where an RNG weakness
323 : : * leads directly to private key exposure unless this function is used. */
324 : 108 : int BN_generate_dsa_nonce(BIGNUM *out, const BIGNUM *range, const BIGNUM* priv,
325 : : const unsigned char *message, size_t message_len,
326 : : BN_CTX *ctx)
327 : : {
328 : : SHA512_CTX sha;
329 : : /* We use 512 bits of random data per iteration to
330 : : * ensure that we have at least |range| bits of randomness. */
331 : : unsigned char random_bytes[64];
332 : : unsigned char digest[SHA512_DIGEST_LENGTH];
333 : : unsigned done, todo;
334 : : /* We generate |range|+8 bytes of random output. */
335 : 108 : const unsigned num_k_bytes = BN_num_bytes(range) + 8;
336 : : unsigned char private_bytes[96];
337 : : unsigned char *k_bytes;
338 : 108 : int ret = 0;
339 : :
340 : 108 : k_bytes = OPENSSL_malloc(num_k_bytes);
341 [ + - ]: 108 : if (!k_bytes)
342 : : goto err;
343 : :
344 : : /* We copy |priv| into a local buffer to avoid exposing its length. */
345 : 108 : todo = sizeof(priv->d[0])*priv->top;
346 [ - + ]: 108 : if (todo > sizeof(private_bytes))
347 : : {
348 : : /* No reasonable DSA or ECDSA key should have a private key
349 : : * this large and we don't handle this case in order to avoid
350 : : * leaking the length of the private key. */
351 : 0 : BNerr(BN_F_BN_GENERATE_DSA_NONCE, BN_R_PRIVATE_KEY_TOO_LARGE);
352 : 0 : goto err;
353 : : }
354 : 108 : memcpy(private_bytes, priv->d, todo);
355 : 108 : memset(private_bytes + todo, 0, sizeof(private_bytes) - todo);
356 : :
357 [ + + ]: 221 : for (done = 0; done < num_k_bytes;) {
358 [ + - ]: 113 : if (RAND_bytes(random_bytes, sizeof(random_bytes)) != 1)
359 : : goto err;
360 : 113 : SHA512_Init(&sha);
361 : 113 : SHA512_Update(&sha, &done, sizeof(done));
362 : 113 : SHA512_Update(&sha, private_bytes, sizeof(private_bytes));
363 : 113 : SHA512_Update(&sha, message, message_len);
364 : 113 : SHA512_Update(&sha, random_bytes, sizeof(random_bytes));
365 : 113 : SHA512_Final(digest, &sha);
366 : :
367 : 113 : todo = num_k_bytes - done;
368 [ + + ]: 113 : if (todo > SHA512_DIGEST_LENGTH)
369 : 5 : todo = SHA512_DIGEST_LENGTH;
370 : 113 : memcpy(k_bytes + done, digest, todo);
371 : 113 : done += todo;
372 : : }
373 : :
374 [ + - ]: 108 : if (!BN_bin2bn(k_bytes, num_k_bytes, out))
375 : : goto err;
376 [ + - ]: 108 : if (BN_mod(out, out, range, ctx) != 1)
377 : : goto err;
378 : 108 : ret = 1;
379 : :
380 : : err:
381 [ + - ]: 108 : if (k_bytes)
382 : 108 : OPENSSL_free(k_bytes);
383 : 108 : return ret;
384 : : }
385 : : #endif /* OPENSSL_NO_SHA512 */
|
