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