2c958d9d48a48194d641c9a40dd10d15e7add4eb
[gnupg.git] / cipher / random.c
1 /* random.c  -  random number generator
2  *      Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
3  *
4  * This file is part of GnuPG.
5  *
6  * GnuPG 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  * GnuPG 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 <time.h>
36 #include <sys/time.h>
37 #include <sys/types.h>
38 #include <sys/stat.h>
39 #include <unistd.h>
40 #include <fcntl.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 "util.h"
54 #include "rmd.h"
55 #include "ttyio.h"
56 #include "i18n.h"
57 #include "random.h"
58 #include "rand-internal.h"
59 #include "dynload.h"
60
61
62 #ifndef RAND_MAX   /* for SunOS */
63   #define RAND_MAX 32767
64 #endif
65
66
67 #if SIZEOF_UNSIGNED_LONG == 8
68   #define ADD_VALUE 0xa5a5a5a5a5a5a5a5
69 #elif SIZEOF_UNSIGNED_LONG == 4
70   #define ADD_VALUE 0xa5a5a5a5
71 #else
72   #error weird size for an unsigned long
73 #endif
74
75 #define BLOCKLEN  64   /* hash this amount of bytes */
76 #define DIGESTLEN 20   /* into a digest of this length (rmd160) */
77 /* poolblocks is the number of digests which make up the pool
78  * and poolsize must be a multiple of the digest length
79  * to make the AND operations faster, the size should also be
80  * a multiple of ulong
81  */
82 #define POOLBLOCKS 30
83 #define POOLSIZE (POOLBLOCKS*DIGESTLEN)
84 #if (POOLSIZE % SIZEOF_UNSIGNED_LONG)
85   #error Please make sure that poolsize is a multiple of ulong
86 #endif
87 #define POOLWORDS (POOLSIZE / SIZEOF_UNSIGNED_LONG)
88
89
90 static int is_initialized;
91 #define MASK_LEVEL(a) do {if( a > 2 ) a = 2; else if( a < 0 ) a = 0; } while(0)
92 static char *rndpool;   /* allocated size is POOLSIZE+BLOCKLEN */
93 static char *keypool;   /* allocated size is POOLSIZE+BLOCKLEN */
94 static size_t pool_readpos;
95 static size_t pool_writepos;
96 static int pool_filled;
97 static int pool_balance;
98 static int just_mixed;
99 static int did_initial_extra_seeding;
100 static char *seed_file_name;
101 static int allow_seed_file_update;
102
103 static int secure_alloc;
104 static int quick_test;
105 static int faked_rng;
106
107
108 static void read_pool( byte *buffer, size_t length, int level );
109 static void add_randomness( const void *buffer, size_t length, int source );
110 static void random_poll(void);
111 static void read_random_source( int requester, size_t length, int level);
112 static int gather_faked( void (*add)(const void*, size_t, int), int requester,
113                                                     size_t length, int level );
114
115 static struct {
116     ulong mixrnd;
117     ulong mixkey;
118     ulong slowpolls;
119     ulong fastpolls;
120     ulong getbytes1;
121     ulong ngetbytes1;
122     ulong getbytes2;
123     ulong ngetbytes2;
124     ulong addbytes;
125     ulong naddbytes;
126 } rndstats;
127
128 static void
129 initialize(void)
130 {
131     /* The data buffer is allocated somewhat larger, so that
132      * we can use this extra space (which is allocated in secure memory)
133      * as a temporary hash buffer */
134     rndpool = secure_alloc ? m_alloc_secure_clear(POOLSIZE+BLOCKLEN)
135                            : m_alloc_clear(POOLSIZE+BLOCKLEN);
136     keypool = secure_alloc ? m_alloc_secure_clear(POOLSIZE+BLOCKLEN)
137                            : m_alloc_clear(POOLSIZE+BLOCKLEN);
138     is_initialized = 1;
139     cipher_modules_constructor();
140 }
141
142 static void
143 burn_stack (int bytes)
144 {
145     char buf[128];
146     
147     memset (buf, 0, sizeof buf);
148     bytes -= sizeof buf;
149     if (bytes > 0)
150         burn_stack (bytes);
151 }
152
153 void
154 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 secure_random_alloc()
167 {
168     secure_alloc = 1;
169 }
170
171
172 int
173 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 randomize_buffer( byte *buffer, size_t length, int level )
192 {
193     char *p = get_random_bits( length*8, level, 1 );
194     memcpy( buffer, p, length );
195     m_free(p);
196 }
197
198
199 int
200 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 byte *
213 get_random_bits( size_t nbits, int level, int secure )
214 {
215     byte *buf, *p;
216     size_t nbytes = (nbits+7)/8;
217
218     if( quick_test && level > 1 )
219         level = 1;
220     MASK_LEVEL(level);
221     if( level == 1 ) {
222         rndstats.getbytes1 += nbytes;
223         rndstats.ngetbytes1++;
224     }
225     else if( level >= 2 ) {
226         rndstats.getbytes2 += nbytes;
227         rndstats.ngetbytes2++;
228     }
229
230     buf = secure && secure_alloc ? m_alloc_secure( nbytes ) : m_alloc( 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
241 /****************
242  * Mix the pool
243  */
244 static void
245 mix_pool(byte *pool)
246 {
247     char *hashbuf = pool + POOLSIZE;
248     char *p, *pend;
249     int i, n;
250     RMD160_CONTEXT md;
251
252     rmd160_init( &md );
253  #if DIGESTLEN != 20
254     #error must have a digest length of 20 for ripe-md-160
255  #endif
256     /* loop over the pool */
257     pend = pool + POOLSIZE;
258     memcpy(hashbuf, pend - DIGESTLEN, DIGESTLEN );
259     memcpy(hashbuf+DIGESTLEN, pool, BLOCKLEN-DIGESTLEN);
260     rmd160_mixblock( &md, hashbuf);
261     memcpy(pool, hashbuf, 20 );
262
263     p = pool;
264     for( n=1; n < POOLBLOCKS; n++ ) {
265         memcpy(hashbuf, p, DIGESTLEN );
266
267         p += DIGESTLEN;
268         if( p+DIGESTLEN+BLOCKLEN < pend )
269             memcpy(hashbuf+DIGESTLEN, p+DIGESTLEN, BLOCKLEN-DIGESTLEN);
270         else {
271             char *pp = p+DIGESTLEN;
272             for(i=DIGESTLEN; i < BLOCKLEN; i++ ) {
273                 if( pp >= pend )
274                     pp = pool;
275                 hashbuf[i] = *pp++;
276             }
277         }
278
279         rmd160_mixblock( &md, hashbuf);
280         memcpy(p, hashbuf, 20 );
281     }
282     burn_stack (384); /* for the rmd160_mixblock() */
283 }
284
285
286 void
287 set_random_seed_file( const char *name )
288 {
289     if( seed_file_name )
290         BUG();
291     seed_file_name = m_strdup( name );
292 }
293
294 /****************
295  * Read in a seed form the random_seed file
296  * and return true if this was successful
297  */
298 static int
299 read_seed_file(void)
300 {
301     int fd;
302     struct stat sb;
303     unsigned char buffer[POOLSIZE];
304     int n;
305
306     if( !seed_file_name )
307         return 0;
308
309   #ifdef HAVE_DOSISH_SYSTEM
310     fd = open( seed_file_name, O_RDONLY | O_BINARY );
311   #else
312     fd = open( seed_file_name, O_RDONLY );
313   #endif
314     if( fd == -1 && errno == ENOENT) {
315         allow_seed_file_update = 1;
316         return 0;
317     }
318
319     if( fd == -1 ) {
320         log_info(_("can't open `%s': %s\n"), seed_file_name, strerror(errno) );
321         return 0;
322     }
323     if( fstat( fd, &sb ) ) {
324         log_info(_("can't stat `%s': %s\n"), seed_file_name, strerror(errno) );
325         close(fd);
326         return 0;
327     }
328     if( !S_ISREG(sb.st_mode) ) {
329         log_info(_("`%s' is not a regular file - ignored\n"), seed_file_name );
330         close(fd);
331         return 0;
332     }
333     if( !sb.st_size ) {
334         log_info(_("note: random_seed file is empty\n") );
335         close(fd);
336         allow_seed_file_update = 1;
337         return 0;
338     }
339     if( sb.st_size != POOLSIZE ) {
340         log_info(_("WARNING: invalid size of random_seed file - not used\n") );
341         close(fd);
342         return 0;
343     }
344     do {
345         n = read( fd, buffer, POOLSIZE );
346     } while( n == -1 && errno == EINTR );
347     if( n != POOLSIZE ) {
348         log_fatal(_("can't read `%s': %s\n"), seed_file_name,strerror(errno) );
349         close(fd);
350         return 0;
351     }
352
353     close(fd);
354
355     add_randomness( buffer, POOLSIZE, 0 );
356     /* add some minor entropy to the pool now (this will also force a mixing) */
357     {   pid_t x = getpid();
358         add_randomness( &x, sizeof(x), 0 );
359     }
360     {   time_t x = time(NULL);
361         add_randomness( &x, sizeof(x), 0 );
362     }
363     {   clock_t x = clock();
364         add_randomness( &x, sizeof(x), 0 );
365     }
366     /* And read a few bytes from our entropy source.  By using
367      * a level of 0 this will not block and might not return anything
368      * with some entropy drivers, however the rndlinux driver will use
369      * /dev/urandom and return some stuff - Do not read to much as we
370      * want to be friendly to the scare system entropy resource. */
371     read_random_source( 0, 16, 0 );
372
373     allow_seed_file_update = 1;
374     return 1;
375 }
376
377 void
378 update_random_seed_file()
379 {
380     ulong *sp, *dp;
381     int fd, i;
382
383     if( !seed_file_name || !is_initialized || !pool_filled )
384         return;
385     if( !allow_seed_file_update ) {
386         log_info(_("note: random_seed file not updated\n"));
387         return;
388     }
389
390
391     /* copy the entropy pool to a scratch pool and mix both of them */
392     for(i=0,dp=(ulong*)keypool, sp=(ulong*)rndpool;
393                                     i < POOLWORDS; i++, dp++, sp++ ) {
394         *dp = *sp + ADD_VALUE;
395     }
396     mix_pool(rndpool); rndstats.mixrnd++;
397     mix_pool(keypool); rndstats.mixkey++;
398
399   #ifdef HAVE_DOSISH_SYSTEM
400     fd = open( seed_file_name, O_WRONLY|O_CREAT|O_TRUNC|O_BINARY,
401                                                         S_IRUSR|S_IWUSR );
402   #else
403     fd = open( seed_file_name, O_WRONLY|O_CREAT|O_TRUNC, S_IRUSR|S_IWUSR );
404   #endif
405     if( fd == -1 ) {
406         log_info(_("can't create `%s': %s\n"), seed_file_name, strerror(errno) );
407         return;
408     }
409     do {
410         i = write( fd, keypool, POOLSIZE );
411     } while( i == -1 && errno == EINTR );
412     if( i != POOLSIZE ) {
413         log_info(_("can't write `%s': %s\n"), seed_file_name, strerror(errno) );
414     }
415     if( close(fd) )
416         log_info(_("can't close `%s': %s\n"), seed_file_name, strerror(errno) );
417 }
418
419
420 static void
421 read_pool( byte *buffer, size_t length, int level )
422 {
423     int i;
424     ulong *sp, *dp;
425
426     if( length > POOLSIZE ) {
427         log_bug("too many random bits requested\n");
428     }
429
430     if( !pool_filled ) {
431         if( read_seed_file() )
432             pool_filled = 1;
433     }
434
435     /* For level 2 quality (key generation) we alwas make
436      * sure that the pool has been seeded enough initially */
437     if( level == 2 && !did_initial_extra_seeding ) {
438         size_t needed;
439
440         pool_balance = 0;
441         needed = length - pool_balance;
442         if( needed < POOLSIZE/2 )
443             needed = POOLSIZE/2;
444         else if( needed > POOLSIZE )
445             BUG();
446         read_random_source( 3, needed, 2 );
447         pool_balance += needed;
448         did_initial_extra_seeding=1;
449     }
450
451     /* for level 2 make sure that there is enough random in the pool */
452     if( level == 2 && pool_balance < length ) {
453         size_t needed;
454
455         if( pool_balance < 0 )
456             pool_balance = 0;
457         needed = length - pool_balance;
458         if( needed > POOLSIZE )
459             BUG();
460         read_random_source( 3, needed, 2 );
461         pool_balance += needed;
462     }
463
464     /* make sure the pool is filled */
465     while( !pool_filled )
466         random_poll();
467
468     /* do always a fast random poll */
469     fast_random_poll();
470
471     if( !level ) { /* no need for cryptographic strong random */
472         /* create a new pool */
473         for(i=0,dp=(ulong*)keypool, sp=(ulong*)rndpool;
474                                     i < POOLWORDS; i++, dp++, sp++ )
475             *dp = *sp + ADD_VALUE;
476         /* must mix both pools */
477         mix_pool(rndpool); rndstats.mixrnd++;
478         mix_pool(keypool); rndstats.mixkey++;
479         memcpy( buffer, keypool, length );
480     }
481     else {
482         /* mix the pool (if add_randomness() didn't it) */
483         if( !just_mixed ) {
484             mix_pool(rndpool);
485             rndstats.mixrnd++;
486         }
487         /* create a new pool */
488         for(i=0,dp=(ulong*)keypool, sp=(ulong*)rndpool;
489                                     i < POOLWORDS; i++, dp++, sp++ )
490             *dp = *sp + ADD_VALUE;
491         /* and mix both pools */
492         mix_pool(rndpool); rndstats.mixrnd++;
493         mix_pool(keypool); rndstats.mixkey++;
494         /* read the required data
495          * we use a readpoiter to read from a different postion each
496          * time */
497         while( length-- ) {
498             *buffer++ = keypool[pool_readpos++];
499             if( pool_readpos >= POOLSIZE )
500                 pool_readpos = 0;
501             pool_balance--;
502         }
503         if( pool_balance < 0 )
504             pool_balance = 0;
505         /* and clear the keypool */
506         memset( keypool, 0, POOLSIZE );
507     }
508 }
509
510
511 /****************
512  * Add LENGTH bytes of randomness from buffer to the pool.
513  * source may be used to specify the randomness source.
514  * Source is:
515  *      0 - used ony for initialization
516  *      1 - fast random poll function
517  *      2 - normal poll function
518  *      3 - used when level 2 random quality has been requested
519  *          to do an extra pool seed.
520  */
521 static void
522 add_randomness( const void *buffer, size_t length, int source )
523 {
524     const byte *p = buffer;
525
526     if( !is_initialized )
527         initialize();
528     rndstats.addbytes += length;
529     rndstats.naddbytes++;
530     while( length-- ) {
531         rndpool[pool_writepos++] ^= *p++;
532         if( pool_writepos >= POOLSIZE ) {
533             if( source > 1 )
534                 pool_filled = 1;
535             pool_writepos = 0;
536             mix_pool(rndpool); rndstats.mixrnd++;
537             just_mixed = !length;
538         }
539     }
540 }
541
542
543
544 static void
545 random_poll()
546 {
547     rndstats.slowpolls++;
548     read_random_source( 2, POOLSIZE/5, 1 );
549 }
550
551
552 void
553 fast_random_poll()
554 {
555     static void (*fnc)( void (*)(const void*, size_t, int), int) = NULL;
556     static int initialized = 0;
557
558     rndstats.fastpolls++;
559     if( !initialized ) {
560         if( !is_initialized )
561             initialize();
562         initialized = 1;
563         fnc = dynload_getfnc_fast_random_poll();
564     }
565     if( fnc ) {
566         (*fnc)( add_randomness, 1 );
567         return;
568     }
569
570     /* fall back to the generic function */
571   #if defined(HAVE_GETHRTIME) && !defined(HAVE_BROKEN_GETHRTIME)
572     {   hrtime_t tv;
573         /* On some Solaris and HPUX system gethrtime raises an SIGILL, but we 
574          * checked this with configure */
575         tv = gethrtime();
576         add_randomness( &tv, sizeof(tv), 1 );
577     }
578   #elif defined (HAVE_GETTIMEOFDAY)
579     {   struct timeval tv;
580         if( gettimeofday( &tv, NULL ) )
581             BUG();
582         add_randomness( &tv.tv_sec, sizeof(tv.tv_sec), 1 );
583         add_randomness( &tv.tv_usec, sizeof(tv.tv_usec), 1 );
584     }
585   #elif defined (HAVE_CLOCK_GETTIME)
586     {   struct timespec tv;
587         if( clock_gettime( CLOCK_REALTIME, &tv ) == -1 )
588             BUG();
589         add_randomness( &tv.tv_sec, sizeof(tv.tv_sec), 1 );
590         add_randomness( &tv.tv_nsec, sizeof(tv.tv_nsec), 1 );
591     }
592   #else /* use times */
593     #ifndef HAVE_DOSISH_SYSTEM
594     {   struct tms buf;
595         times( &buf );
596         add_randomness( &buf, sizeof buf, 1 );
597     }
598     #endif
599   #endif
600   #ifdef HAVE_GETRUSAGE
601     #ifndef RUSAGE_SELF
602       #ifdef __GCC__
603         #warning There is no RUSAGE_SELF on this system
604       #endif
605     #else
606     {   struct rusage buf;
607         /* QNX/Neutrino does return ENOSYS - so we just ignore it and
608          * add whatever is in buf.  In a chroot environment it might not
609          * work at all (i.e. because /proc/ is not accessible), so we better 
610          * ignore all error codes and hope for the best
611          */
612         getrusage( RUSAGE_SELF, &buf );
613         
614         add_randomness( &buf, sizeof buf, 1 );
615         memset( &buf, 0, sizeof buf );
616     }
617     #endif
618   #endif
619     /* time and clock are available on all systems - so
620      * we better do it just in case one of the above functions
621      * didn't work */
622     {   time_t x = time(NULL);
623         add_randomness( &x, sizeof(x), 1 );
624     }
625     {   clock_t x = clock();
626         add_randomness( &x, sizeof(x), 1 );
627     }
628 }
629
630
631
632 static void
633 read_random_source( int requester, size_t length, int level )
634 {
635     static int (*fnc)(void (*)(const void*, size_t, int), int,
636                                                     size_t, int) = NULL;
637     if( !fnc ) {
638         if( !is_initialized )
639             initialize();
640         fnc = dynload_getfnc_gather_random();
641         if( !fnc ) {
642             faked_rng = 1;
643             fnc = gather_faked;
644         }
645         if( !requester && !length && !level )
646             return; /* init only */
647     }
648     if( (*fnc)( add_randomness, requester, length, level ) < 0 )
649         log_fatal("No way to gather entropy for the RNG\n");
650 }
651
652
653 static int
654 gather_faked( void (*add)(const void*, size_t, int), int requester,
655               size_t length, int level )
656 {
657     static int initialized=0;
658     size_t n;
659     char *buffer, *p;
660
661     if( !initialized ) {
662         log_info(_("WARNING: using insecure random number generator!!\n"));
663         tty_printf(_("The random number generator is only a kludge to let\n"
664                    "it run - it is in no way a strong RNG!\n\n"
665                    "DON'T USE ANY DATA GENERATED BY THIS PROGRAM!!\n\n"));
666         initialized=1;
667       #ifdef HAVE_RAND
668         srand(make_timestamp()*getpid());
669       #else
670         srandom(make_timestamp()*getpid());
671       #endif
672     }
673
674     p = buffer = m_alloc( length );
675     n = length;
676   #ifdef HAVE_RAND
677     while( n-- )
678         *p++ = ((unsigned)(1 + (int) (256.0*rand()/(RAND_MAX+1.0)))-1);
679   #else
680     while( n-- )
681         *p++ = ((unsigned)(1 + (int) (256.0*random()/(RAND_MAX+1.0)))-1);
682   #endif
683     add_randomness( buffer, length, requester );
684     m_free(buffer);
685     return 0; /* okay */
686 }
687