5c48bf6da9361a14302bfd17bc5c89cb4765bca4
[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_bug("too many random bits requested\n");
439     }
440
441     if( !pool_filled ) {
442         if( read_seed_file() )
443             pool_filled = 1;
444     }
445
446     /* For level 2 quality (key generation) we alwas make
447      * sure that the pool has been seeded enough initially */
448     if( level == 2 && !did_initial_extra_seeding ) {
449         size_t needed;
450
451         pool_balance = 0;
452         needed = length - pool_balance;
453         if( needed < POOLSIZE/2 )
454             needed = POOLSIZE/2;
455         else if( needed > POOLSIZE )
456             BUG();
457         read_random_source( 3, needed, 2 );
458         pool_balance += needed;
459         did_initial_extra_seeding=1;
460     }
461
462     /* for level 2 make sure that there is enough random in the pool */
463     if( level == 2 && pool_balance < length ) {
464         size_t needed;
465
466         if( pool_balance < 0 )
467             pool_balance = 0;
468         needed = length - pool_balance;
469         if( needed > POOLSIZE )
470             BUG();
471         read_random_source( 3, needed, 2 );
472         pool_balance += needed;
473     }
474
475     /* make sure the pool is filled */
476     while( !pool_filled )
477         random_poll();
478
479     /* do always a fast random poll */
480     fast_random_poll();
481
482     if( !level ) { /* no need for cryptographic strong random */
483         /* create a new pool */
484         for(i=0,dp=(ulong*)keypool, sp=(ulong*)rndpool;
485                                     i < POOLWORDS; i++, dp++, sp++ )
486             *dp = *sp + ADD_VALUE;
487         /* must mix both pools */
488         mix_pool(rndpool); rndstats.mixrnd++;
489         mix_pool(keypool); rndstats.mixkey++;
490         memcpy( buffer, keypool, length );
491     }
492     else {
493         /* mix the pool (if add_randomness() didn't it) */
494         if( !just_mixed ) {
495             mix_pool(rndpool);
496             rndstats.mixrnd++;
497         }
498         /* create a new pool */
499         for(i=0,dp=(ulong*)keypool, sp=(ulong*)rndpool;
500                                     i < POOLWORDS; i++, dp++, sp++ )
501             *dp = *sp + ADD_VALUE;
502         /* and mix both pools */
503         mix_pool(rndpool); rndstats.mixrnd++;
504         mix_pool(keypool); rndstats.mixkey++;
505         /* read the required data
506          * we use a readpoiter to read from a different postion each
507          * time */
508         while( length-- ) {
509             *buffer++ = keypool[pool_readpos++];
510             if( pool_readpos >= POOLSIZE )
511                 pool_readpos = 0;
512             pool_balance--;
513         }
514         if( pool_balance < 0 )
515             pool_balance = 0;
516         /* and clear the keypool */
517         memset( keypool, 0, POOLSIZE );
518     }
519 }
520
521
522 /****************
523  * Add LENGTH bytes of randomness from buffer to the pool.
524  * source may be used to specify the randomness source.
525  * Source is:
526  *      0 - used ony for initialization
527  *      1 - fast random poll function
528  *      2 - normal poll function
529  *      3 - used when level 2 random quality has been requested
530  *          to do an extra pool seed.
531  */
532 static void
533 add_randomness( const void *buffer, size_t length, int source )
534 {
535     const byte *p = buffer;
536
537     if( !is_initialized )
538         initialize();
539     rndstats.addbytes += length;
540     rndstats.naddbytes++;
541     while( length-- ) {
542         rndpool[pool_writepos++] = *p++;
543         if( pool_writepos >= POOLSIZE ) {
544             if( source > 1 )
545                 pool_filled = 1;
546             pool_writepos = 0;
547             mix_pool(rndpool); rndstats.mixrnd++;
548             just_mixed = !length;
549         }
550     }
551 }
552
553
554
555 static void
556 random_poll()
557 {
558     rndstats.slowpolls++;
559     read_random_source( 2, POOLSIZE/5, 1 );
560 }
561
562
563 void
564 _gcry_fast_random_poll()
565 {
566     static void (*fnc)( void (*)(const void*, size_t, int), int) = NULL;
567     static int initialized = 0;
568
569     rndstats.fastpolls++;
570     if( !initialized ) {
571         if( !is_initialized )
572             initialize();
573         initialized = 1;
574         fnc = _gcry_dynload_getfnc_fast_random_poll();
575     }
576     if( fnc ) {
577         (*fnc)( add_randomness, 1 );
578         return;
579     }
580
581     /* fall back to the generic function */
582   #if HAVE_GETHRTIME
583     {   hrtime_t tv;
584         tv = gethrtime();
585         add_randomness( &tv, sizeof(tv), 1 );
586     }
587   #elif HAVE_GETTIMEOFDAY
588     {   struct timeval tv;
589         if( gettimeofday( &tv, NULL ) )
590             BUG();
591         add_randomness( &tv.tv_sec, sizeof(tv.tv_sec), 1 );
592         add_randomness( &tv.tv_usec, sizeof(tv.tv_usec), 1 );
593     }
594   #elif HAVE_CLOCK_GETTIME
595     {   struct timespec tv;
596         if( clock_gettime( CLOCK_REALTIME, &tv ) == -1 )
597             BUG();
598         add_randomness( &tv.tv_sec, sizeof(tv.tv_sec), 1 );
599         add_randomness( &tv.tv_nsec, sizeof(tv.tv_nsec), 1 );
600     }
601   #else /* use times */
602     #ifndef HAVE_DOSISH_SYSTEM
603     {   struct tms buf;
604         times( &buf );
605         add_randomness( &buf, sizeof buf, 1 );
606     }
607     #endif
608   #endif
609   #ifdef HAVE_GETRUSAGE
610     #ifndef RUSAGE_SELF
611       #ifdef __GCC__
612         #warning There is no RUSAGE_SELF on this system
613       #endif
614     #else
615     {   
616         struct rusage buf;
617         /* QNX/Neutrino does return ENOSYS - so we just ignore it and
618          * add whatever is in buf.  In a chroot environment it might not
619          * work at all (i.e. because /proc/ is not accessible), so we better 
620          * ugnore all error codes and hope for the best
621          */
622         getrusage (RUSAGE_SELF, &buf );
623         add_randomness( &buf, sizeof buf, 1 );
624         memset( &buf, 0, sizeof buf );
625     }
626     #endif
627   #endif
628     /* time and clock are availabe on all systems - so
629      * we better do it just in case one of the above functions
630      * didn't work */
631     {   time_t x = time(NULL);
632         add_randomness( &x, sizeof(x), 1 );
633     }
634     {   clock_t x = clock();
635         add_randomness( &x, sizeof(x), 1 );
636     }
637 }
638
639
640
641 static void
642 read_random_source( int requester, size_t length, int level )
643 {
644     static int (*fnc)(void (*)(const void*, size_t, int), int,
645                                                     size_t, int) = NULL;
646     if( !fnc ) {
647         if( !is_initialized )
648             initialize();
649         fnc = _gcry_dynload_getfnc_gather_random();
650         if( !fnc ) {
651             faked_rng = 1;
652             fnc = gather_faked;
653         }
654         if( !requester && !length && !level )
655             return; /* init only */
656     }
657     if( (*fnc)( add_randomness, requester, length, level ) < 0 )
658         log_fatal("No way to gather entropy for the RNG\n");
659 }
660
661
662 static int
663 gather_faked( void (*add)(const void*, size_t, int), int requester,
664               size_t length, int level )
665 {
666     static int initialized=0;
667     size_t n;
668     char *buffer, *p;
669
670     if( !initialized ) {
671         log_info(_("WARNING: using insecure random number generator!!\n"));
672         /* we can't use tty_printf here - do we need this function at
673           all - does it really make sense or canit be viewed as a potential
674           security problem ? wk 17.11.99 */
675 #if __GNUC__ >= 2
676 #     warning Extended warning disabled
677 #endif
678       #if 0
679         tty_printf(_("The random number generator is only a kludge to let\n"
680                    "it run - it is in no way a strong RNG!\n\n"
681                    "DON'T USE ANY DATA GENERATED BY THIS PROGRAM!!\n\n"));
682       #endif
683         initialized=1;
684       #ifdef HAVE_RAND
685         srand( time(NULL)*getpid());
686       #else
687         srandom( time(NULL)*getpid());
688       #endif
689     }
690
691     p = buffer = gcry_xmalloc( length );
692     n = length;
693   #ifdef HAVE_RAND
694     while( n-- )
695         *p++ = ((unsigned)(1 + (int) (256.0*rand()/(RAND_MAX+1.0)))-1);
696   #else
697     while( n-- )
698         *p++ = ((unsigned)(1 + (int) (256.0*random()/(RAND_MAX+1.0)))-1);
699   #endif
700     add_randomness( buffer, length, requester );
701     gcry_free(buffer);
702     return 0; /* okay */
703 }
704