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