1
/* random.c - random number generator
2
* Copyright (C) 1998, 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
4
* This file is part of GnuPG.
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.
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.
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
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".
37
#include <sys/types.h>
42
#include <sys/times.h>
44
#ifdef HAVE_GETTIMEOFDAY
45
#include <sys/times.h>
48
#include <sys/resource.h>
58
#include "rand-internal.h"
59
#include "algorithms.h"
61
#ifndef RAND_MAX /* for SunOS */
62
#define RAND_MAX 32767
66
#if SIZEOF_UNSIGNED_LONG == 8
67
#define ADD_VALUE 0xa5a5a5a5a5a5a5a5
68
#elif SIZEOF_UNSIGNED_LONG == 4
69
#define ADD_VALUE 0xa5a5a5a5
71
#error weird size for an unsigned long
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
82
#define POOLSIZE (POOLBLOCKS*DIGESTLEN)
83
#if (POOLSIZE % SIZEOF_UNSIGNED_LONG)
84
#error Please make sure that poolsize is a multiple of ulong
86
#define POOLWORDS (POOLSIZE / SIZEOF_UNSIGNED_LONG)
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;
102
static int secure_alloc;
103
static int quick_test;
104
static int faked_rng;
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 );
129
getfnc_gather_random (void))(void (*)(const void*, size_t, int), int,
132
#ifdef USE_ALL_RANDOM_MODULES
133
static int (*fnc)(void (*)(const void*, size_t, int), int, size_t, int);
138
if ( !access (NAME_OF_DEV_RANDOM, R_OK)
139
&& !access (NAME_OF_DEV_RANDOM, R_OK))
141
fnc = rndlinux_gather_random;
146
if ( rndegd_connect_socket (1) != -1 )
148
fnc = rndegd_gather_random;
153
fnc = rndunix_gather_random;
157
log_fatal (_("no entropy gathering module detected\n"));
161
return rndlinux_gather_random;
164
return rndunix_gather_random;
167
return rndegd_gather_random;
170
return rndw32_gather_random;
172
# ifdef USE_RNDRISCOS
173
return rndriscos_gather_random;
180
getfnc_fast_random_poll (void))( void (*)(const void*, size_t, int), int)
183
return rndw32_gather_random_fast;
193
/* The data buffer is allocated somewhat larger, so that
194
* we can use this extra space (which is allocated in secure memory)
195
* as a temporary hash buffer */
196
rndpool = secure_alloc ? m_alloc_secure_clear(POOLSIZE+BLOCKLEN)
197
: m_alloc_clear(POOLSIZE+BLOCKLEN);
198
keypool = secure_alloc ? m_alloc_secure_clear(POOLSIZE+BLOCKLEN)
199
: m_alloc_clear(POOLSIZE+BLOCKLEN);
204
burn_stack (int bytes)
208
memset (buf, 0, sizeof buf);
218
"random usage: poolsize=%d mixed=%lu polls=%lu/%lu added=%lu/%lu\n"
219
" outmix=%lu getlvl1=%lu/%lu getlvl2=%lu/%lu\n",
220
POOLSIZE, rndstats.mixrnd, rndstats.slowpolls, rndstats.fastpolls,
221
rndstats.naddbytes, rndstats.addbytes,
222
rndstats.mixkey, rndstats.ngetbytes1, rndstats.getbytes1,
223
rndstats.ngetbytes2, rndstats.getbytes2 );
227
secure_random_alloc()
234
quick_random_gen( int onoff )
238
read_random_source(0,0,0); /* init */
242
return faked_rng? 1 : last;
247
* Fill the buffer with LENGTH bytes of cryptographically strong
248
* random bytes. level 0 is not very strong, 1 is strong enough
249
* for most usage, 2 is good for key generation stuff but may be very slow.
252
randomize_buffer( byte *buffer, size_t length, int level )
254
char *p = get_random_bits( length*8, level, 1 );
255
memcpy( buffer, p, length );
263
if( !is_initialized )
265
return faked_rng || quick_test;
269
* Return a pointer to a randomized buffer of level 0 and LENGTH bits
270
* caller must free the buffer.
271
* Note: The returned value is rounded up to bytes.
274
get_random_bits( size_t nbits, int level, int secure )
277
size_t nbytes = (nbits+7)/8;
279
if( quick_test && level > 1 )
283
rndstats.getbytes1 += nbytes;
284
rndstats.ngetbytes1++;
286
else if( level >= 2 ) {
287
rndstats.getbytes2 += nbytes;
288
rndstats.ngetbytes2++;
291
buf = secure && secure_alloc ? m_alloc_secure( nbytes ) : m_alloc( nbytes );
292
for( p = buf; nbytes > 0; ) {
293
size_t n = nbytes > POOLSIZE? POOLSIZE : nbytes;
294
read_pool( p, n, level );
308
char *hashbuf = pool + POOLSIZE;
315
#error must have a digest length of 20 for ripe-md-160
317
/* loop over the pool */
318
pend = pool + POOLSIZE;
319
memcpy(hashbuf, pend - DIGESTLEN, DIGESTLEN );
320
memcpy(hashbuf+DIGESTLEN, pool, BLOCKLEN-DIGESTLEN);
321
rmd160_mixblock( &md, hashbuf);
322
memcpy(pool, hashbuf, 20 );
325
for( n=1; n < POOLBLOCKS; n++ ) {
326
memcpy(hashbuf, p, DIGESTLEN );
329
if( p+DIGESTLEN+BLOCKLEN < pend )
330
memcpy(hashbuf+DIGESTLEN, p+DIGESTLEN, BLOCKLEN-DIGESTLEN);
332
char *pp = p+DIGESTLEN;
333
for(i=DIGESTLEN; i < BLOCKLEN; i++ ) {
340
rmd160_mixblock( &md, hashbuf);
341
memcpy(p, hashbuf, 20 );
343
burn_stack (384); /* for the rmd160_mixblock() */
348
set_random_seed_file( const char *name )
352
seed_file_name = m_strdup( name );
356
* Read in a seed form the random_seed file
357
* and return true if this was successful
364
unsigned char buffer[POOLSIZE];
367
if( !seed_file_name )
370
#ifdef HAVE_DOSISH_SYSTEM
371
fd = open( seed_file_name, O_RDONLY | O_BINARY );
373
fd = open( seed_file_name, O_RDONLY );
375
if( fd == -1 && errno == ENOENT) {
376
allow_seed_file_update = 1;
381
log_info(_("can't open `%s': %s\n"), seed_file_name, strerror(errno) );
384
if( fstat( fd, &sb ) ) {
385
log_info(_("can't stat `%s': %s\n"), seed_file_name, strerror(errno) );
389
if( !S_ISREG(sb.st_mode) ) {
390
log_info(_("`%s' is not a regular file - ignored\n"), seed_file_name );
395
log_info(_("note: random_seed file is empty\n") );
397
allow_seed_file_update = 1;
400
if( sb.st_size != POOLSIZE ) {
401
log_info(_("WARNING: invalid size of random_seed file - not used\n") );
406
n = read( fd, buffer, POOLSIZE );
407
} while( n == -1 && errno == EINTR );
408
if( n != POOLSIZE ) {
409
log_fatal(_("can't read `%s': %s\n"), seed_file_name,strerror(errno) );
416
add_randomness( buffer, POOLSIZE, 0 );
417
/* add some minor entropy to the pool now (this will also force a mixing) */
418
{ pid_t x = getpid();
419
add_randomness( &x, sizeof(x), 0 );
421
{ time_t x = time(NULL);
422
add_randomness( &x, sizeof(x), 0 );
424
{ clock_t x = clock();
425
add_randomness( &x, sizeof(x), 0 );
427
/* And read a few bytes from our entropy source. By using
428
* a level of 0 this will not block and might not return anything
429
* with some entropy drivers, however the rndlinux driver will use
430
* /dev/urandom and return some stuff - Do not read to much as we
431
* want to be friendly to the scare system entropy resource. */
432
read_random_source( 0, 16, 0 );
434
allow_seed_file_update = 1;
439
update_random_seed_file()
444
if( !seed_file_name || !is_initialized || !pool_filled )
446
if( !allow_seed_file_update ) {
447
log_info(_("note: random_seed file not updated\n"));
452
/* copy the entropy pool to a scratch pool and mix both of them */
453
for(i=0,dp=(ulong*)keypool, sp=(ulong*)rndpool;
454
i < POOLWORDS; i++, dp++, sp++ ) {
455
*dp = *sp + ADD_VALUE;
457
mix_pool(rndpool); rndstats.mixrnd++;
458
mix_pool(keypool); rndstats.mixkey++;
460
#ifdef HAVE_DOSISH_SYSTEM
461
fd = open( seed_file_name, O_WRONLY|O_CREAT|O_TRUNC|O_BINARY,
464
fd = open( seed_file_name, O_WRONLY|O_CREAT|O_TRUNC, S_IRUSR|S_IWUSR );
467
log_info(_("can't create `%s': %s\n"), seed_file_name, strerror(errno) );
471
i = write( fd, keypool, POOLSIZE );
472
} while( i == -1 && errno == EINTR );
473
if( i != POOLSIZE ) {
474
log_info(_("can't write `%s': %s\n"), seed_file_name, strerror(errno) );
477
log_info(_("can't close `%s': %s\n"), seed_file_name, strerror(errno) );
482
read_pool( byte *buffer, size_t length, int level )
487
if( length > POOLSIZE ) {
488
log_bug("too many random bits requested\n");
492
if( read_seed_file() )
496
/* For level 2 quality (key generation) we alwas make
497
* sure that the pool has been seeded enough initially */
498
if( level == 2 && !did_initial_extra_seeding ) {
502
needed = length - pool_balance;
503
if( needed < POOLSIZE/2 )
505
else if( needed > POOLSIZE )
507
read_random_source( 3, needed, 2 );
508
pool_balance += needed;
509
did_initial_extra_seeding=1;
512
/* for level 2 make sure that there is enough random in the pool */
513
if( level == 2 && pool_balance < length ) {
516
if( pool_balance < 0 )
518
needed = length - pool_balance;
519
if( needed > POOLSIZE )
521
read_random_source( 3, needed, 2 );
522
pool_balance += needed;
525
/* make sure the pool is filled */
526
while( !pool_filled )
529
/* do always a fast random poll */
532
if( !level ) { /* no need for cryptographic strong random */
533
/* create a new pool */
534
for(i=0,dp=(ulong*)keypool, sp=(ulong*)rndpool;
535
i < POOLWORDS; i++, dp++, sp++ )
536
*dp = *sp + ADD_VALUE;
537
/* must mix both pools */
538
mix_pool(rndpool); rndstats.mixrnd++;
539
mix_pool(keypool); rndstats.mixkey++;
540
memcpy( buffer, keypool, length );
543
/* mix the pool (if add_randomness() didn't it) */
548
/* create a new pool */
549
for(i=0,dp=(ulong*)keypool, sp=(ulong*)rndpool;
550
i < POOLWORDS; i++, dp++, sp++ )
551
*dp = *sp + ADD_VALUE;
552
/* and mix both pools */
553
mix_pool(rndpool); rndstats.mixrnd++;
554
mix_pool(keypool); rndstats.mixkey++;
555
/* read the required data
556
* we use a readpoiter to read from a different postion each
559
*buffer++ = keypool[pool_readpos++];
560
if( pool_readpos >= POOLSIZE )
564
if( pool_balance < 0 )
566
/* and clear the keypool */
567
memset( keypool, 0, POOLSIZE );
573
* Add LENGTH bytes of randomness from buffer to the pool.
574
* source may be used to specify the randomness source.
576
* 0 - used ony for initialization
577
* 1 - fast random poll function
578
* 2 - normal poll function
579
* 3 - used when level 2 random quality has been requested
580
* to do an extra pool seed.
583
add_randomness( const void *buffer, size_t length, int source )
585
const byte *p = buffer;
587
if( !is_initialized )
589
rndstats.addbytes += length;
590
rndstats.naddbytes++;
592
rndpool[pool_writepos++] ^= *p++;
593
if( pool_writepos >= POOLSIZE ) {
597
mix_pool(rndpool); rndstats.mixrnd++;
598
just_mixed = !length;
608
rndstats.slowpolls++;
609
read_random_source( 2, POOLSIZE/5, 1 );
616
static void (*fnc)( void (*)(const void*, size_t, int), int) = NULL;
617
static int initialized = 0;
619
rndstats.fastpolls++;
621
if( !is_initialized )
624
fnc = getfnc_fast_random_poll();
627
(*fnc)( add_randomness, 1 );
631
/* fall back to the generic function */
632
#if defined(HAVE_GETHRTIME) && !defined(HAVE_BROKEN_GETHRTIME)
634
/* On some Solaris and HPUX system gethrtime raises an SIGILL, but we
635
* checked this with configure */
637
add_randomness( &tv, sizeof(tv), 1 );
639
#elif defined (HAVE_GETTIMEOFDAY)
641
if( gettimeofday( &tv, NULL ) )
643
add_randomness( &tv.tv_sec, sizeof(tv.tv_sec), 1 );
644
add_randomness( &tv.tv_usec, sizeof(tv.tv_usec), 1 );
646
#elif defined (HAVE_CLOCK_GETTIME)
647
{ struct timespec tv;
648
if( clock_gettime( CLOCK_REALTIME, &tv ) == -1 )
650
add_randomness( &tv.tv_sec, sizeof(tv.tv_sec), 1 );
651
add_randomness( &tv.tv_nsec, sizeof(tv.tv_nsec), 1 );
653
#else /* use times */
654
#ifndef HAVE_DOSISH_SYSTEM
657
add_randomness( &buf, sizeof buf, 1 );
661
#ifdef HAVE_GETRUSAGE
664
#warning There is no RUSAGE_SELF on this system
668
/* QNX/Neutrino does return ENOSYS - so we just ignore it and
669
* add whatever is in buf. In a chroot environment it might not
670
* work at all (i.e. because /proc/ is not accessible), so we better
671
* ignore all error codes and hope for the best
673
getrusage( RUSAGE_SELF, &buf );
675
add_randomness( &buf, sizeof buf, 1 );
676
memset( &buf, 0, sizeof buf );
680
/* time and clock are available on all systems - so
681
* we better do it just in case one of the above functions
683
{ time_t x = time(NULL);
684
add_randomness( &x, sizeof(x), 1 );
686
{ clock_t x = clock();
687
add_randomness( &x, sizeof(x), 1 );
694
read_random_source( int requester, size_t length, int level )
696
static int (*fnc)(void (*)(const void*, size_t, int), int,
699
if( !is_initialized )
701
fnc = getfnc_gather_random();
706
if( !requester && !length && !level )
707
return; /* init only */
709
if( (*fnc)( add_randomness, requester, length, level ) < 0 )
710
log_fatal("No way to gather entropy for the RNG\n");
715
gather_faked( void (*add)(const void*, size_t, int), int requester,
716
size_t length, int level )
718
static int initialized=0;
723
log_info(_("WARNING: using insecure random number generator!!\n"));
724
tty_printf(_("The random number generator is only a kludge to let\n"
725
"it run - it is in no way a strong RNG!\n\n"
726
"DON'T USE ANY DATA GENERATED BY THIS PROGRAM!!\n\n"));
729
srand(make_timestamp()*getpid());
731
srandom(make_timestamp()*getpid());
735
p = buffer = m_alloc( length );
739
*p++ = ((unsigned)(1 + (int) (256.0*rand()/(RAND_MAX+1.0)))-1);
742
*p++ = ((unsigned)(1 + (int) (256.0*random()/(RAND_MAX+1.0)))-1);
744
add_randomness( buffer, length, requester );