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