Import OpenSSL-1.0.1d.
[dragonfly.git] / crypto / openssl / crypto / rand / md_rand.c
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
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
157 const char RAND_version[]="RAND" OPENSSL_VERSION_PTEXT;
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
167 RAND_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
176 RAND_METHOD *RAND_SSLeay(void)
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;
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
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;
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
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
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
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
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         }