source: trunk/sys/libcrypto/others/md_rand.c @ 301

Last change on this file since 301 was 1, checked in by alain, 8 years ago

First import

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