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