1/* crypto/rand/md_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_FIPSEVP
113
114#ifdef MD_RAND_DEBUG
115# ifndef NDEBUG
116# define NDEBUG
117# endif
118#endif
119
120#include <assert.h>
121#include <stdio.h>
122#include <string.h>
123
124#include "e_os.h"
125
126#include <openssl/crypto.h>
127#include <openssl/rand.h>
128#include "rand_lcl.h"
129
130#include <openssl/err.h>
131
132#ifdef BN_DEBUG
133# define PREDICT
134#endif
135
136/* #define PREDICT 1 */
137
138#define STATE_SIZE 1023
139static int state_num=0,state_index=0;
140static unsigned char state[STATE_SIZE+MD_DIGEST_LENGTH];
141static unsigned char md[MD_DIGEST_LENGTH];
142static long md_count[2]={0,0};
143static double entropy=0;
144static int initialized=0;
145
146static unsigned int crypto_lock_rand = 0; /* may be set only when a thread
147 * holds CRYPTO_LOCK_RAND
148 * (to prevent double locking) */
149/* access to lockin_thread is synchronized by CRYPTO_LOCK_RAND2 */
150static CRYPTO_THREADID locking_threadid; /* valid iff crypto_lock_rand is set */
151
152
153#ifdef PREDICT
154int rand_predictable=0;
155#endif
156
157const char RAND_version[]="RAND" OPENSSL_VERSION_PTEXT;
158
159static void ssleay_rand_cleanup(void);
160static void ssleay_rand_seed(const void *buf, int num);
161static void ssleay_rand_add(const void *buf, int num, double add_entropy);
162static int ssleay_rand_bytes(unsigned char *buf, int num, int pseudo);
163static int ssleay_rand_nopseudo_bytes(unsigned char *buf, int num);
164static int ssleay_rand_pseudo_bytes(unsigned char *buf, int num);
165static int ssleay_rand_status(void);
166
167RAND_METHOD rand_ssleay_meth={
168 ssleay_rand_seed,
169 ssleay_rand_nopseudo_bytes,
170 ssleay_rand_cleanup,
171 ssleay_rand_add,
172 ssleay_rand_pseudo_bytes,
173 ssleay_rand_status
174 };
175
176RAND_METHOD *RAND_SSLeay(void)
177 {
178 return(&rand_ssleay_meth);
179 }
180
181static void ssleay_rand_cleanup(void)
182 {
183 OPENSSL_cleanse(state,sizeof(state));
184 state_num=0;
185 state_index=0;
186 OPENSSL_cleanse(md,MD_DIGEST_LENGTH);
187 md_count[0]=0;
188 md_count[1]=0;
189 entropy=0;
190 initialized=0;
191 }
192
193static void ssleay_rand_add(const void *buf, int num, double add)
194 {
195 int i,j,k,st_idx;
196 long md_c[2];
197 unsigned char local_md[MD_DIGEST_LENGTH];
198 EVP_MD_CTX m;
199 int do_not_lock;
200
201 /*
202 * (Based on the rand(3) manpage)
203 *
204 * The input is chopped up into units of 20 bytes (or less for
205 * the last block). Each of these blocks is run through the hash
206 * function as follows: The data passed to the hash function
207 * is the current 'md', the same number of bytes from the 'state'
208 * (the location determined by in incremented looping index) as
209 * the current 'block', the new key data 'block', and 'count'
210 * (which is incremented after each use).
211 * The result of this is kept in 'md' and also xored into the
212 * 'state' at the same locations that were used as input into the
213 * hash function.
214 */
215
216 /* check if we already have the lock */
217 if (crypto_lock_rand)
218 {
219 CRYPTO_THREADID cur;
220 CRYPTO_THREADID_current(&cur);
221 CRYPTO_r_lock(CRYPTO_LOCK_RAND2);
222 do_not_lock = !CRYPTO_THREADID_cmp(&locking_threadid, &cur);
223 CRYPTO_r_unlock(CRYPTO_LOCK_RAND2);
224 }
225 else
226 do_not_lock = 0;
227
228 if (!do_not_lock) CRYPTO_w_lock(CRYPTO_LOCK_RAND);
229 st_idx=state_index;
230
231 /* use our own copies of the counters so that even
232 * if a concurrent thread seeds with exactly the
233 * same data and uses the same subarray there's _some_
234 * difference */
235 md_c[0] = md_count[0];
236 md_c[1] = md_count[1];
237
238 memcpy(local_md, md, sizeof md);
239
240 /* state_index <= state_num <= STATE_SIZE */
241 state_index += num;
242 if (state_index >= STATE_SIZE)
243 {
244 state_index%=STATE_SIZE;
245 state_num=STATE_SIZE;
246 }
247 else if (state_num < STATE_SIZE)
248 {
249 if (state_index > state_num)
250 state_num=state_index;
251 }
252 /* state_index <= state_num <= STATE_SIZE */
253
254 /* state[st_idx], ..., state[(st_idx + num - 1) % STATE_SIZE]
255 * are what we will use now, but other threads may use them
256 * as well */
257
258 md_count[1] += (num / MD_DIGEST_LENGTH) + (num % MD_DIGEST_LENGTH > 0);
259
260 if (!do_not_lock) CRYPTO_w_unlock(CRYPTO_LOCK_RAND);
261
262 EVP_MD_CTX_init(&m);
263 for (i=0; i<num; i+=MD_DIGEST_LENGTH)
264 {
265 j=(num-i);
266 j=(j > MD_DIGEST_LENGTH)?MD_DIGEST_LENGTH:j;
267
268 MD_Init(&m);
269 MD_Update(&m,local_md,MD_DIGEST_LENGTH);
270 k=(st_idx+j)-STATE_SIZE;
271 if (k > 0)
272 {
273 MD_Update(&m,&(state[st_idx]),j-k);
274 MD_Update(&m,&(state[0]),k);
275 }
276 else
277 MD_Update(&m,&(state[st_idx]),j);
278
279 /* DO NOT REMOVE THE FOLLOWING CALL TO MD_Update()! */
280 MD_Update(&m,buf,j);
281 /* We know that line may cause programs such as
282 purify and valgrind to complain about use of
283 uninitialized data. The problem is not, it's
284 with the caller. Removing that line will make
285 sure you get really bad randomness and thereby
286 other problems such as very insecure keys. */
287
288 MD_Update(&m,(unsigned char *)&(md_c[0]),sizeof(md_c));
289 MD_Final(&m,local_md);
290 md_c[1]++;
291
292 buf=(const char *)buf + j;
293
294 for (k=0; k<j; k++)
295 {
296 /* Parallel threads may interfere with this,
297 * but always each byte of the new state is
298 * the XOR of some previous value of its
299 * and local_md (itermediate values may be lost).
300 * Alway using locking could hurt performance more
301 * than necessary given that conflicts occur only
302 * when the total seeding is longer than the random
303 * state. */
304 state[st_idx++]^=local_md[k];
305 if (st_idx >= STATE_SIZE)
306 st_idx=0;
307 }
308 }
309 EVP_MD_CTX_cleanup(&m);
310
311 if (!do_not_lock) CRYPTO_w_lock(CRYPTO_LOCK_RAND);
312 /* Don't just copy back local_md into md -- this could mean that
313 * other thread's seeding remains without effect (except for
314 * the incremented counter). By XORing it we keep at least as
315 * much entropy as fits into md. */
316 for (k = 0; k < (int)sizeof(md); k++)
317 {
318 md[k] ^= local_md[k];
319 }
320 if (entropy < ENTROPY_NEEDED) /* stop counting when we have enough */
321 entropy += add;
322 if (!do_not_lock) CRYPTO_w_unlock(CRYPTO_LOCK_RAND);
323
324#if !defined(OPENSSL_THREADS) && !defined(OPENSSL_SYS_WIN32)
325 assert(md_c[1] == md_count[1]);
326#endif
327 }
328
329static void ssleay_rand_seed(const void *buf, int num)
330 {
331 ssleay_rand_add(buf, num, (double)num);
332 }
333
334static int ssleay_rand_bytes(unsigned char *buf, int num, int pseudo)
335 {
336 static volatile int stirred_pool = 0;
337 int i,j,k,st_num,st_idx;
338 int num_ceil;
339 int ok;
340 long md_c[2];
341 unsigned char local_md[MD_DIGEST_LENGTH];
342 EVP_MD_CTX m;
343#ifndef GETPID_IS_MEANINGLESS
344 pid_t curr_pid = getpid();
345#endif
346 int do_stir_pool = 0;
347
348#ifdef PREDICT
349 if (rand_predictable)
350 {
351 static unsigned char val=0;
352
353 for (i=0; i<num; i++)
354 buf[i]=val++;
355 return(1);
356 }
357#endif
358
359 if (num <= 0)
360 return 1;
361
362 EVP_MD_CTX_init(&m);
363 /* round upwards to multiple of MD_DIGEST_LENGTH/2 */
364 num_ceil = (1 + (num-1)/(MD_DIGEST_LENGTH/2)) * (MD_DIGEST_LENGTH/2);
365
366 /*
367 * (Based on the rand(3) manpage:)
368 *
369 * For each group of 10 bytes (or less), we do the following:
370 *
371 * Input into the hash function the local 'md' (which is initialized from
372 * the global 'md' before any bytes are generated), the bytes that are to
373 * be overwritten by the random bytes, and bytes from the 'state'
374 * (incrementing looping index). From this digest output (which is kept
375 * in 'md'), the top (up to) 10 bytes are returned to the caller and the
376 * bottom 10 bytes are xored into the 'state'.
377 *
378 * Finally, after we have finished 'num' random bytes for the
379 * caller, 'count' (which is incremented) and the local and global 'md'
380 * are fed into the hash function and the results are kept in the
381 * global 'md'.
382 */
383
384 CRYPTO_w_lock(CRYPTO_LOCK_RAND);
385
386 /* prevent ssleay_rand_bytes() from trying to obtain the lock again */
387 CRYPTO_w_lock(CRYPTO_LOCK_RAND2);
388 CRYPTO_THREADID_current(&locking_threadid);
389 CRYPTO_w_unlock(CRYPTO_LOCK_RAND2);
390 crypto_lock_rand = 1;
391
392 if (!initialized)
393 {
394 RAND_poll();
395 initialized = 1;
396 }
397
398 if (!stirred_pool)
399 do_stir_pool = 1;
400
401 ok = (entropy >= ENTROPY_NEEDED);
402 if (!ok)
403 {
404 /* If the PRNG state is not yet unpredictable, then seeing
405 * the PRNG output may help attackers to determine the new
406 * state; thus we have to decrease the entropy estimate.
407 * Once we've had enough initial seeding we don't bother to
408 * adjust the entropy count, though, because we're not ambitious
409 * to provide *information-theoretic* randomness.
410 *
411 * NOTE: This approach fails if the program forks before
412 * we have enough entropy. Entropy should be collected
413 * in a separate input pool and be transferred to the
414 * output pool only when the entropy limit has been reached.
415 */
416 entropy -= num;
417 if (entropy < 0)
418 entropy = 0;
419 }
420
421 if (do_stir_pool)
422 {
423 /* In the output function only half of 'md' remains secret,
424 * so we better make sure that the required entropy gets
425 * 'evenly distributed' through 'state', our randomness pool.
426 * The input function (ssleay_rand_add) chains all of 'md',
427 * which makes it more suitable for this purpose.
428 */
429
430 int n = STATE_SIZE; /* so that the complete pool gets accessed */
431 while (n > 0)
432 {
433#if MD_DIGEST_LENGTH > 20
434# error "Please adjust DUMMY_SEED."
435#endif
436#define DUMMY_SEED "...................." /* at least MD_DIGEST_LENGTH */
437 /* Note that the seed does not matter, it's just that
438 * ssleay_rand_add expects to have something to hash. */
439 ssleay_rand_add(DUMMY_SEED, MD_DIGEST_LENGTH, 0.0);
440 n -= MD_DIGEST_LENGTH;
441 }
442 if (ok)
443 stirred_pool = 1;
444 }
445
446 st_idx=state_index;
447 st_num=state_num;
448 md_c[0] = md_count[0];
449 md_c[1] = md_count[1];
450 memcpy(local_md, md, sizeof md);
451
452 state_index+=num_ceil;
453 if (state_index > state_num)
454 state_index %= state_num;
455
456 /* state[st_idx], ..., state[(st_idx + num_ceil - 1) % st_num]
457 * are now ours (but other threads may use them too) */
458
459 md_count[0] += 1;
460
461 /* before unlocking, we must clear 'crypto_lock_rand' */
462 crypto_lock_rand = 0;
463 CRYPTO_w_unlock(CRYPTO_LOCK_RAND);
464
465 while (num > 0)
466 {
467 /* num_ceil -= MD_DIGEST_LENGTH/2 */
468 j=(num >= MD_DIGEST_LENGTH/2)?MD_DIGEST_LENGTH/2:num;
469 num-=j;
470 MD_Init(&m);
471#ifndef GETPID_IS_MEANINGLESS
472 if (curr_pid) /* just in the first iteration to save time */
473 {
474 MD_Update(&m,(unsigned char*)&curr_pid,sizeof curr_pid);
475 curr_pid = 0;
476 }
477#endif
478 MD_Update(&m,local_md,MD_DIGEST_LENGTH);
479 MD_Update(&m,(unsigned char *)&(md_c[0]),sizeof(md_c));
480
481#ifndef PURIFY /* purify complains */
482 /* The following line uses the supplied buffer as a small
483 * source of entropy: since this buffer is often uninitialised
484 * it may cause programs such as purify or valgrind to
485 * complain. So for those builds it is not used: the removal
486 * of such a small source of entropy has negligible impact on
487 * security.
488 */
489 MD_Update(&m,buf,j);
490#endif
491
492 k=(st_idx+MD_DIGEST_LENGTH/2)-st_num;
493 if (k > 0)
494 {
495 MD_Update(&m,&(state[st_idx]),MD_DIGEST_LENGTH/2-k);
496 MD_Update(&m,&(state[0]),k);
497 }
498 else
499 MD_Update(&m,&(state[st_idx]),MD_DIGEST_LENGTH/2);
500 MD_Final(&m,local_md);
501
502 for (i=0; i<MD_DIGEST_LENGTH/2; i++)
503 {
504 state[st_idx++]^=local_md[i]; /* may compete with other threads */
505 if (st_idx >= st_num)
506 st_idx=0;
507 if (i < j)
508 *(buf++)=local_md[i+MD_DIGEST_LENGTH/2];
509 }
510 }
511
512 MD_Init(&m);
513 MD_Update(&m,(unsigned char *)&(md_c[0]),sizeof(md_c));
514 MD_Update(&m,local_md,MD_DIGEST_LENGTH);
515 CRYPTO_w_lock(CRYPTO_LOCK_RAND);
516 MD_Update(&m,md,MD_DIGEST_LENGTH);
517 MD_Final(&m,md);
518 CRYPTO_w_unlock(CRYPTO_LOCK_RAND);
519
520 EVP_MD_CTX_cleanup(&m);
521 if (ok)
522 return(1);
523 else if (pseudo)
524 return 0;
525 else
526 {
527 RANDerr(RAND_F_SSLEAY_RAND_BYTES,RAND_R_PRNG_NOT_SEEDED);
528 ERR_add_error_data(1, "You need to read the OpenSSL FAQ, "
529 "http://www.openssl.org/support/faq.html");
530 return(0);
531 }
532 }
533
534static int ssleay_rand_nopseudo_bytes(unsigned char *buf, int num)
535 {
536 return ssleay_rand_bytes(buf, num, 0);
537 }
538
539/* pseudo-random bytes that are guaranteed to be unique but not
540 unpredictable */
541static int ssleay_rand_pseudo_bytes(unsigned char *buf, int num)
542 {
543 return ssleay_rand_bytes(buf, num, 1);
544 }
545
546static int ssleay_rand_status(void)
547 {
548 CRYPTO_THREADID cur;
549 int ret;
550 int do_not_lock;
551
552 CRYPTO_THREADID_current(&cur);
553 /* check if we already have the lock
554 * (could happen if a RAND_poll() implementation calls RAND_status()) */
555 if (crypto_lock_rand)
556 {
557 CRYPTO_r_lock(CRYPTO_LOCK_RAND2);
558 do_not_lock = !CRYPTO_THREADID_cmp(&locking_threadid, &cur);
559 CRYPTO_r_unlock(CRYPTO_LOCK_RAND2);
560 }
561 else
562 do_not_lock = 0;
563
564 if (!do_not_lock)
565 {
566 CRYPTO_w_lock(CRYPTO_LOCK_RAND);
567
568 /* prevent ssleay_rand_bytes() from trying to obtain the lock again */
569 CRYPTO_w_lock(CRYPTO_LOCK_RAND2);
570 CRYPTO_THREADID_cpy(&locking_threadid, &cur);
571 CRYPTO_w_unlock(CRYPTO_LOCK_RAND2);
572 crypto_lock_rand = 1;
573 }
574
575 if (!initialized)
576 {
577 RAND_poll();
578 initialized = 1;
579 }
580
581 ret = entropy >= ENTROPY_NEEDED;
582
583 if (!do_not_lock)
584 {
585 /* before unlocking, we must clear 'crypto_lock_rand' */
586 crypto_lock_rand = 0;
587
588 CRYPTO_w_unlock(CRYPTO_LOCK_RAND);
589 }
590
591 return ret;
592 }
593