OpenSSL  1.0.1c
 All Classes Files Functions Variables Typedefs Enumerations Enumerator Macros
md_rand.c
Go to the documentation of this file.
1 /* crypto/rand/md_rand.c */
2 /* Copyright (C) 1995-1998 Eric Young ([email protected])
3  * All rights reserved.
4  *
5  * This package is an SSL implementation written
6  * by Eric Young ([email protected]).
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 ([email protected]).
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 ([email protected])"
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 ([email protected])"
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
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  * ([email protected]). This product includes software written by Tim
108  * Hudson ([email protected]).
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/rand.h>
127 #include "rand_lcl.h"
128 
129 #include <openssl/crypto.h>
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
139 static int state_num=0,state_index=0;
140 static unsigned char state[STATE_SIZE+MD_DIGEST_LENGTH];
141 static unsigned char md[MD_DIGEST_LENGTH];
142 static long md_count[2]={0,0};
143 static double entropy=0;
144 static int initialized=0;
145 
146 static 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 */
150 static CRYPTO_THREADID locking_threadid; /* valid iff crypto_lock_rand is set */
151 
152 
153 #ifdef PREDICT
154 int rand_predictable=0;
155 #endif
156 
158 
159 static void ssleay_rand_cleanup(void);
160 static void ssleay_rand_seed(const void *buf, int num);
161 static void ssleay_rand_add(const void *buf, int num, double add_entropy);
162 static int ssleay_rand_bytes(unsigned char *buf, int num, int pseudo);
163 static int ssleay_rand_nopseudo_bytes(unsigned char *buf, int num);
164 static int ssleay_rand_pseudo_bytes(unsigned char *buf, int num);
165 static int ssleay_rand_status(void);
166 
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 
177  {
178  return(&rand_ssleay_meth);
179  }
180 
181 static void ssleay_rand_cleanup(void)
182  {
183  OPENSSL_cleanse(state,sizeof(state));
184  state_num=0;
185  state_index=0;
187  md_count[0]=0;
188  md_count[1]=0;
189  entropy=0;
190  initialized=0;
191  }
192 
193 static 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;
222  do_not_lock = !CRYPTO_THREADID_cmp(&locking_threadid, &cur);
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);
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 
329 static void ssleay_rand_seed(const void *buf, int num)
330  {
331  ssleay_rand_add(buf, num, (double)num);
332  }
333 
334 static 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 
385 
386  /* prevent ssleay_rand_bytes() from trying to obtain the lock again */
388  CRYPTO_THREADID_current(&locking_threadid);
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;
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);
517  MD_Final(&m,md);
519 
520  EVP_MD_CTX_cleanup(&m);
521  if (ok)
522  return(1);
523  else if (pseudo)
524  return 0;
525  else
526  {
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 
534 static 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 */
541 static int ssleay_rand_pseudo_bytes(unsigned char *buf, int num)
542  {
543  return ssleay_rand_bytes(buf, num, 1);
544  }
545 
546 static int ssleay_rand_status(void)
547  {
548  CRYPTO_THREADID cur;
549  int ret;
550  int do_not_lock;
551 
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  {
558  do_not_lock = !CRYPTO_THREADID_cmp(&locking_threadid, &cur);
560  }
561  else
562  do_not_lock = 0;
563 
564  if (!do_not_lock)
565  {
567 
568  /* prevent ssleay_rand_bytes() from trying to obtain the lock again */
570  CRYPTO_THREADID_cpy(&locking_threadid, &cur);
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 
589  }
590 
591  return ret;
592  }