Applied changes from GnuPG stable.
[libgcrypt.git] / cipher / random.c
1 /* random.c  -  random number generator
2  *      Copyright (C) 1998, 2000, 2001 Free Software Foundation, Inc.
3  *
4  * This file is part of Libgcrypt.
5  *
6  * Libgcrypt is free software; you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License as published by
8  * the Free Software Foundation; either version 2 of the License, or
9  * (at your option) any later version.
10  *
11  * Libgcrypt is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software
18  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
19  */
20
21
22 /****************
23  * This random number generator is modelled after the one described
24  * in Peter Gutmann's Paper: "Software Generation of Practically
25  * Strong Random Numbers".
26  */
27
28
29 #include <config.h>
30 #include <stdio.h>
31 #include <stdlib.h>
32 #include <assert.h>
33 #include <errno.h>
34 #include <string.h>
35 #include <sys/time.h>
36 #include <sys/types.h>
37 #include <sys/stat.h>
38 #include <unistd.h>
39 #include <fcntl.h>
40 #include <time.h>
41 #ifdef  HAVE_GETHRTIME
42   #include <sys/times.h>
43 #endif
44 #ifdef HAVE_GETTIMEOFDAY
45   #include <sys/times.h>
46 #endif
47 #ifdef HAVE_GETRUSAGE
48   #include <sys/resource.h>
49 #endif
50 #ifdef __MINGW32__
51   #include <process.h>
52 #endif
53 #include "g10lib.h"
54 #include "rmd.h"
55 #include "random.h"
56 #include "rand-internal.h"
57 #include "dynload.h"
58
59
60 #ifndef RAND_MAX   /* for SunOS */
61   #define RAND_MAX 32767
62 #endif
63
64
65 #if SIZEOF_UNSIGNED_LONG == 8
66   #define ADD_VALUE 0xa5a5a5a5a5a5a5a5
67 #elif SIZEOF_UNSIGNED_LONG == 4
68   #define ADD_VALUE 0xa5a5a5a5
69 #else
70   #error weird size for an unsigned long
71 #endif
72
73 #define BLOCKLEN  64   /* hash this amount of bytes */
74 #define DIGESTLEN 20   /* into a digest of this length (rmd160) */
75 /* poolblocks is the number of digests which make up the pool
76  * and poolsize must be a multiple of the digest length
77  * to make the AND operations faster, the size should also be
78  * a multiple of ulong
79  */
80 #define POOLBLOCKS 30
81 #define POOLSIZE (POOLBLOCKS*DIGESTLEN)
82 #if (POOLSIZE % SIZEOF_UNSIGNED_LONG)
83   #error Please make sure that poolsize is a multiple of ulong
84 #endif
85 #define POOLWORDS (POOLSIZE / SIZEOF_UNSIGNED_LONG)
86
87
88 static int is_initialized;
89 #define MASK_LEVEL(a) do {if( a > 2 ) a = 2; else if( a < 0 ) a = 0; } while(0)
90 static char *rndpool;   /* allocated size is POOLSIZE+BLOCKLEN */
91 static char *keypool;   /* allocated size is POOLSIZE+BLOCKLEN */
92 static size_t pool_readpos;
93 static size_t pool_writepos;
94 static int pool_filled;
95 static int pool_balance;
96 static int just_mixed;
97 static int did_initial_extra_seeding;
98 static char *seed_file_name;
99 static int allow_seed_file_update;
100
101 static int secure_alloc;
102 static int quick_test;
103 static int faked_rng;
104
105
106 static byte *get_random_bytes( size_t nbytes, int level, int secure );
107 static void read_pool( byte *buffer, size_t length, int level );
108 static void add_randomness( const void *buffer, size_t length, int source );
109 static void random_poll(void);
110 static void read_random_source( int requester, size_t length, int level);
111 static int gather_faked( void (*add)(const void*, size_t, int), int requester,
112                                                     size_t length, int level );
113
114 static struct {
115     ulong mixrnd;
116     ulong mixkey;
117     ulong slowpolls;
118     ulong fastpolls;
119     ulong getbytes1;
120     ulong ngetbytes1;
121     ulong getbytes2;
122     ulong ngetbytes2;
123     ulong addbytes;
124     ulong naddbytes;
125 } rndstats;
126
127 static void
128 initialize(void)
129 {
130     /* The data buffer is allocated somewhat larger, so that
131      * we can use this extra space (which is allocated in secure memory)
132      * as a temporary hash buffer */
133     rndpool = secure_alloc ? gcry_xcalloc_secure(1,POOLSIZE+BLOCKLEN)
134                            : gcry_xcalloc(1,POOLSIZE+BLOCKLEN);
135     keypool = secure_alloc ? gcry_xcalloc_secure(1,POOLSIZE+BLOCKLEN)
136                            : gcry_xcalloc(1,POOLSIZE+BLOCKLEN);
137     is_initialized = 1;
138     _gcry_cipher_modules_constructor();
139 }
140
141 static void
142 burn_stack (int bytes)
143 {
144     char buf[128];
145     
146     memset (buf, 0, sizeof buf);
147     bytes -= sizeof buf;
148     if (bytes > 0)
149         burn_stack (bytes);
150 }
151
152
153 void
154 _gcry_random_dump_stats()
155 {
156     fprintf(stderr,
157             "random usage: poolsize=%d mixed=%lu polls=%lu/%lu added=%lu/%lu\n"
158             "              outmix=%lu getlvl1=%lu/%lu getlvl2=%lu/%lu\n",
159         POOLSIZE, rndstats.mixrnd, rndstats.slowpolls, rndstats.fastpolls,
160                   rndstats.naddbytes, rndstats.addbytes,
161         rndstats.mixkey, rndstats.ngetbytes1, rndstats.getbytes1,
162                     rndstats.ngetbytes2, rndstats.getbytes2 );
163 }
164
165 void
166 _gcry_secure_random_alloc()
167 {
168     secure_alloc = 1;
169 }
170
171
172 int
173 _gcry_quick_random_gen( int onoff )
174 {
175     int last;
176
177     read_random_source(0,0,0); /* init */
178     last = quick_test;
179     if( onoff != -1 )
180         quick_test = onoff;
181     return faked_rng? 1 : last;
182 }
183
184
185 /****************
186  * Fill the buffer with LENGTH bytes of cryptographically strong
187  * random bytes. level 0 is not very strong, 1 is strong enough
188  * for most usage, 2 is good for key generation stuff but may be very slow.
189  */
190 void
191 gcry_randomize( byte *buffer, size_t length, enum gcry_random_level level )
192 {
193     char *p = get_random_bytes( length, level, 1 );
194     memcpy( buffer, p, length );
195     gcry_free(p);
196 }
197
198
199 int
200 _gcry_random_is_faked()
201 {
202     if( !is_initialized )
203         initialize();
204     return faked_rng || quick_test;
205 }
206
207 /****************
208  * Return a pointer to a randomized buffer of level 0 and LENGTH bits
209  * caller must free the buffer.
210  * Note: The returned value is rounded up to bytes.
211  */
212 static byte *
213 get_random_bytes( size_t nbytes, int level, int secure )
214 {
215     byte *buf, *p;
216
217     if( quick_test && level > 1 )
218         level = 1;
219     MASK_LEVEL(level);
220     if( level == 1 ) {
221         rndstats.getbytes1 += nbytes;
222         rndstats.ngetbytes1++;
223     }
224     else if( level >= 2 ) {
225         rndstats.getbytes2 += nbytes;
226         rndstats.ngetbytes2++;
227     }
228
229     buf = secure && secure_alloc ? gcry_xmalloc_secure( nbytes )
230                                  : gcry_xmalloc( nbytes );
231     for( p = buf; nbytes > 0; ) {
232         size_t n = nbytes > POOLSIZE? POOLSIZE : nbytes;
233         read_pool( p, n, level );
234         nbytes -= n;
235         p += n;
236     }
237     return buf;
238 }
239
240 void *
241 gcry_random_bytes( size_t nbytes, enum gcry_random_level level )
242 {
243     return get_random_bytes( nbytes, level, 0 );
244 }
245
246 void *
247 gcry_random_bytes_secure( size_t nbytes, enum gcry_random_level level )
248 {
249     return get_random_bytes( nbytes, level, 1 );
250 }
251
252
253 /****************
254  * Mix the pool
255  */
256 static void
257 mix_pool(byte *pool)
258 {
259     char *hashbuf = pool + POOLSIZE;
260     char *p, *pend;
261     int i, n;
262     RMD160_CONTEXT md;
263
264     _gcry_rmd160_init( &md );
265  #if DIGESTLEN != 20
266     #error must have a digest length of 20 for ripe-md-160
267  #endif
268     /* loop over the pool */
269     pend = pool + POOLSIZE;
270     memcpy(hashbuf, pend - DIGESTLEN, DIGESTLEN );
271     memcpy(hashbuf+DIGESTLEN, pool, BLOCKLEN-DIGESTLEN);
272     _gcry_rmd160_mixblock( &md, hashbuf);
273     memcpy(pool, hashbuf, 20 );
274
275     p = pool;
276     for( n=1; n < POOLBLOCKS; n++ ) {
277         memcpy(hashbuf, p, DIGESTLEN );
278
279         p += DIGESTLEN;
280         if( p+DIGESTLEN+BLOCKLEN < pend )
281             memcpy(hashbuf+DIGESTLEN, p+DIGESTLEN, BLOCKLEN-DIGESTLEN);
282         else {
283             char *pp = p+DIGESTLEN;
284             for(i=DIGESTLEN; i < BLOCKLEN; i++ ) {
285                 if( pp >= pend )
286                     pp = pool;
287                 hashbuf[i] = *pp++;
288             }
289         }
290
291         _gcry_rmd160_mixblock( &md, hashbuf);
292         memcpy(p, hashbuf, 20 );
293     }
294     burn_stack (200); /* for the rmd160_mixblock() */
295 }
296
297 void
298 _gcry_set_random_seed_file( const char *name )
299 {
300     if( seed_file_name )
301         BUG();
302     seed_file_name = gcry_xstrdup( name );
303 }
304
305 /****************
306  * Read in a seed form the random_seed file
307  * and return true if this was successful
308  */
309 static int
310 read_seed_file()
311 {
312     int fd;
313     struct stat sb;
314     unsigned char buffer[POOLSIZE];
315     int n;
316
317     if( !seed_file_name )
318         return 0;
319
320   #ifdef HAVE_DOSISH_SYSTEM
321     fd = open( seed_file_name, O_RDONLY | O_BINARY );
322   #else
323     fd = open( seed_file_name, O_RDONLY );
324   #endif
325     if( fd == -1 && errno == ENOENT) {
326         allow_seed_file_update = 1;
327         return 0;
328     }
329
330     if( fd == -1 ) {
331         log_info(_("can't open `%s': %s\n"), seed_file_name, strerror(errno) );
332         return 0;
333     }
334     if( fstat( fd, &sb ) ) {
335         log_info(_("can't stat `%s': %s\n"), seed_file_name, strerror(errno) );
336         close(fd);
337         return 0;
338     }
339     if( !S_ISREG(sb.st_mode) ) {
340         log_info(_("`%s' is not a regular file - ignored\n"), seed_file_name );
341         close(fd);
342         return 0;
343     }
344     if( !sb.st_size ) {
345         log_info(_("note: random_seed file is empty\n") );
346         close(fd);
347         allow_seed_file_update = 1;
348         return 0;
349     }
350     if( sb.st_size != POOLSIZE ) {
351         log_info(_("warning: invalid size of random_seed file - not used\n") );
352         close(fd);
353         return 0;
354     }
355     do {
356         n = read( fd, buffer, POOLSIZE );
357     } while( n == -1 && errno == EINTR );
358     if( n != POOLSIZE ) {
359         log_fatal(_("can't read `%s': %s\n"), seed_file_name,strerror(errno) );
360         close(fd);
361         return 0;
362     }
363
364     close(fd);
365
366     add_randomness( buffer, POOLSIZE, 0 );
367     /* add some minor entropy to the pool now (this will also force a mixing) */
368     {   pid_t x = getpid();
369         add_randomness( &x, sizeof(x), 0 );
370     }
371     {   time_t x = time(NULL);
372         add_randomness( &x, sizeof(x), 0 );
373     }
374     {   clock_t x = clock();
375         add_randomness( &x, sizeof(x), 0 );
376     }
377     /* And read a few bytes from our entropy source.  By using
378      * a level of 0 this will not block and might not return anything
379      * with some entropy drivers, however the rndlinux driver will use
380      * /dev/urandom and return some stuff - Do not read to much as we
381      * want to be friendly to the scare system entropy resource. */
382     read_random_source( 0, 16, 0 );
383
384     allow_seed_file_update = 1;
385     return 1;
386 }
387
388 void
389 _gcry_update_random_seed_file()
390 {
391     ulong *sp, *dp;
392     int fd, i;
393
394     if( !seed_file_name || !is_initialized || !pool_filled )
395         return;
396     if( !allow_seed_file_update ) {
397         log_info(_("note: random_seed file not updated\n"));
398         return;
399     }
400
401
402     /* copy the entropy pool to a scratch pool and mix both of them */
403     for(i=0,dp=(ulong*)keypool, sp=(ulong*)rndpool;
404                                     i < POOLWORDS; i++, dp++, sp++ ) {
405         *dp = *sp + ADD_VALUE;
406     }
407     mix_pool(rndpool); rndstats.mixrnd++;
408     mix_pool(keypool); rndstats.mixkey++;
409
410   #ifdef HAVE_DOSISH_SYSTEM
411     fd = open( seed_file_name, O_WRONLY|O_CREAT|O_TRUNC|O_BINARY,
412                                                         S_IRUSR|S_IWUSR );
413   #else
414     fd = open( seed_file_name, O_WRONLY|O_CREAT|O_TRUNC, S_IRUSR|S_IWUSR );
415   #endif
416     if( fd == -1 ) {
417         log_info(_("can't create `%s': %s\n"), seed_file_name, strerror(errno) );
418         return;
419     }
420     do {
421         i = write( fd, keypool, POOLSIZE );
422     } while( i == -1 && errno == EINTR );
423     if( i != POOLSIZE ) {
424         log_info(_("can't write `%s': %s\n"), seed_file_name, strerror(errno) );
425     }
426     if( close(fd) )
427         log_info(_("can't close `%s': %s\n"), seed_file_name, strerror(errno) );
428 }
429
430
431 static void
432 read_pool( byte *buffer, size_t length, int level )
433 {
434     int i;
435     ulong *sp, *dp;
436
437     if( length >= POOLSIZE ) {
438         log_fatal(_("too many random bits requested; the limit is %d\n"),
439                   POOLSIZE*8-1 );
440     }
441
442     if( !pool_filled ) {
443         if( read_seed_file() )
444             pool_filled = 1;
445     }
446
447     /* For level 2 quality (key generation) we alwas make
448      * sure that the pool has been seeded enough initially */
449     if( level == 2 && !did_initial_extra_seeding ) {
450         size_t needed;
451
452         pool_balance = 0;
453         needed = length - pool_balance;
454         if( needed < POOLSIZE/2 )
455             needed = POOLSIZE/2;
456         else if( needed > POOLSIZE )
457             BUG();
458         read_random_source( 3, needed, 2 );
459         pool_balance += needed;
460         did_initial_extra_seeding=1;
461     }
462
463     /* for level 2 make sure that there is enough random in the pool */
464     if( level == 2 && pool_balance < length ) {
465         size_t needed;
466
467         if( pool_balance < 0 )
468             pool_balance = 0;
469         needed = length - pool_balance;
470         if( needed > POOLSIZE )
471             BUG();
472         read_random_source( 3, needed, 2 );
473         pool_balance += needed;
474     }
475
476     /* make sure the pool is filled */
477     while( !pool_filled )
478         random_poll();
479
480     /* do always a fast random poll */
481     fast_random_poll();
482
483     if( !level ) { /* no need for cryptographic strong random */
484         /* create a new pool */
485         for(i=0,dp=(ulong*)keypool, sp=(ulong*)rndpool;
486                                     i < POOLWORDS; i++, dp++, sp++ )
487             *dp = *sp + ADD_VALUE;
488         /* must mix both pools */
489         mix_pool(rndpool); rndstats.mixrnd++;
490         mix_pool(keypool); rndstats.mixkey++;
491         memcpy( buffer, keypool, length );
492     }
493     else {
494         /* mix the pool (if add_randomness() didn't it) */
495         if( !just_mixed ) {
496             mix_pool(rndpool);
497             rndstats.mixrnd++;
498         }
499         /* create a new pool */
500         for(i=0,dp=(ulong*)keypool, sp=(ulong*)rndpool;
501                                     i < POOLWORDS; i++, dp++, sp++ )
502             *dp = *sp + ADD_VALUE;
503         /* and mix both pools */
504         mix_pool(rndpool); rndstats.mixrnd++;
505         mix_pool(keypool); rndstats.mixkey++;
506         /* read the required data
507          * we use a readpoiter to read from a different postion each
508          * time */
509         while( length-- ) {
510             *buffer++ = keypool[pool_readpos++];
511             if( pool_readpos >= POOLSIZE )
512                 pool_readpos = 0;
513             pool_balance--;
514         }
515         if( pool_balance < 0 )
516             pool_balance = 0;
517         /* and clear the keypool */
518         memset( keypool, 0, POOLSIZE );
519     }
520 }
521
522
523 /****************
524  * Add LENGTH bytes of randomness from buffer to the pool.
525  * source may be used to specify the randomness source.
526  * Source is:
527  *      0 - used ony for initialization
528  *      1 - fast random poll function
529  *      2 - normal poll function
530  *      3 - used when level 2 random quality has been requested
531  *          to do an extra pool seed.
532  */
533 static void
534 add_randomness( const void *buffer, size_t length, int source )
535 {
536     const byte *p = buffer;
537
538     if( !is_initialized )
539         initialize();
540     rndstats.addbytes += length;
541     rndstats.naddbytes++;
542     while( length-- ) {
543         rndpool[pool_writepos++] = *p++;
544         if( pool_writepos >= POOLSIZE ) {
545             if( source > 1 )
546                 pool_filled = 1;
547             pool_writepos = 0;
548             mix_pool(rndpool); rndstats.mixrnd++;
549             just_mixed = !length;
550         }
551     }
552 }
553
554
555
556 static void
557 random_poll()
558 {
559     rndstats.slowpolls++;
560     read_random_source( 2, POOLSIZE/5, 1 );
561 }
562
563
564 void
565 _gcry_fast_random_poll()
566 {
567     static void (*fnc)( void (*)(const void*, size_t, int), int) = NULL;
568     static int initialized = 0;
569
570     rndstats.fastpolls++;
571     if( !initialized ) {
572         if( !is_initialized )
573             initialize();
574         initialized = 1;
575         fnc = _gcry_dynload_getfnc_fast_random_poll();
576     }
577     if( fnc ) {
578         (*fnc)( add_randomness, 1 );
579         return;
580     }
581
582     /* fall back to the generic function */
583   #if HAVE_GETHRTIME
584     {   hrtime_t tv;
585         tv = gethrtime();
586         add_randomness( &tv, sizeof(tv), 1 );
587     }
588   #elif HAVE_GETTIMEOFDAY
589     {   struct timeval tv;
590         if( gettimeofday( &tv, NULL ) )
591             BUG();
592         add_randomness( &tv.tv_sec, sizeof(tv.tv_sec), 1 );
593         add_randomness( &tv.tv_usec, sizeof(tv.tv_usec), 1 );
594     }
595   #elif HAVE_CLOCK_GETTIME
596     {   struct timespec tv;
597         if( clock_gettime( CLOCK_REALTIME, &tv ) == -1 )
598             BUG();
599         add_randomness( &tv.tv_sec, sizeof(tv.tv_sec), 1 );
600         add_randomness( &tv.tv_nsec, sizeof(tv.tv_nsec), 1 );
601     }
602   #else /* use times */
603     #ifndef HAVE_DOSISH_SYSTEM
604     {   struct tms buf;
605         times( &buf );
606         add_randomness( &buf, sizeof buf, 1 );
607     }
608     #endif
609   #endif
610   #ifdef HAVE_GETRUSAGE
611     #ifndef RUSAGE_SELF
612       #ifdef __GCC__
613         #warning There is no RUSAGE_SELF on this system
614       #endif
615     #else
616     {   
617         struct rusage buf;
618         /* QNX/Neutrino does return ENOSYS - so we just ignore it and
619          * add whatever is in buf.  In a chroot environment it might not
620          * work at all (i.e. because /proc/ is not accessible), so we better 
621          * ugnore all error codes and hope for the best
622          */
623         getrusage (RUSAGE_SELF, &buf );
624         add_randomness( &buf, sizeof buf, 1 );
625         memset( &buf, 0, sizeof buf );
626     }
627     #endif
628   #endif
629     /* time and clock are availabe on all systems - so
630      * we better do it just in case one of the above functions
631      * didn't work */
632     {   time_t x = time(NULL);
633         add_randomness( &x, sizeof(x), 1 );
634     }
635     {   clock_t x = clock();
636         add_randomness( &x, sizeof(x), 1 );
637     }
638 }
639
640
641
642 static void
643 read_random_source( int requester, size_t length, int level )
644 {
645     static int (*fnc)(void (*)(const void*, size_t, int), int,
646                                                     size_t, int) = NULL;
647     if( !fnc ) {
648         if( !is_initialized )
649             initialize();
650         fnc = _gcry_dynload_getfnc_gather_random();
651         if( !fnc ) {
652             faked_rng = 1;
653             fnc = gather_faked;
654         }
655         if( !requester && !length && !level )
656             return; /* init only */
657     }
658     if( (*fnc)( add_randomness, requester, length, level ) < 0 )
659         log_fatal("No way to gather entropy for the RNG\n");
660 }
661
662
663 static int
664 gather_faked( void (*add)(const void*, size_t, int), int requester,
665               size_t length, int level )
666 {
667     static int initialized=0;
668     size_t n;
669     char *buffer, *p;
670
671     if( !initialized ) {
672         log_info(_("WARNING: using insecure random number generator!!\n"));
673         /* we can't use tty_printf here - do we need this function at
674           all - does it really make sense or canit be viewed as a potential
675           security problem ? wk 17.11.99 */
676         #warning Extended warning disabled
677       #if 0
678         tty_printf(_("The random number generator is only a kludge to let\n"
679                    "it run - it is in no way a strong RNG!\n\n"
680                    "DON'T USE ANY DATA GENERATED BY THIS PROGRAM!!\n\n"));
681       #endif
682         initialized=1;
683       #ifdef HAVE_RAND
684         srand( time(NULL)*getpid());
685       #else
686         srandom( time(NULL)*getpid());
687       #endif
688     }
689
690     p = buffer = gcry_xmalloc( length );
691     n = length;
692   #ifdef HAVE_RAND
693     while( n-- )
694         *p++ = ((unsigned)(1 + (int) (256.0*rand()/(RAND_MAX+1.0)))-1);
695   #else
696     while( n-- )
697         *p++ = ((unsigned)(1 + (int) (256.0*random()/(RAND_MAX+1.0)))-1);
698   #endif
699     add_randomness( buffer, length, requester );
700     gcry_free(buffer);
701     return 0; /* okay */
702 }
703