New random generator
Werner Koch
wk at isil.d.shuttle.de
Wed Mar 4 11:17:17 CET 1998
I have partly implemented the random Generator, presented in
in Peter Gutmann's paper "Software Generation of Practically Strong
Random Numbers". I did the mixing/read part and a poll function which uses
/dev/urandom. So you will not get the annoying messages about the lack
of entropy anymore - I'm not sure wether those random number are strong
enough for key generation; the /dev/random device tracks an estimate of
available randomness with an counter of written/read randomness; which is
not used anymore - it may happen that new random bytes only get into the
pool from the fast_random_poll function which adds time an resource
statistics.
As far as I can see, the FIPS about DSA do less than this, they only require
a seed value which is not specified and do some mixing.
So here is the question: Is it safe to use this new function for key
generation?
#define BLOCKLEN 64 /* hash this amount of bytes */
#define DIGESTLEN 20 /* into a digest of this length (rmd160) */
/* poolblocks is the number of digests which make up the pool
* and poolsize must be a multiple of the digest length
* to make the AND operations faster, the size should also be
* a multiple of ulong
*/
#define POOLBLOCKS 30
#define POOLSIZE (POOLBLOCKS*DIGESTLEN)
#if (POOLSIZE % SIZEOF_UNSIGNED_LONG)
#error Please make sure that poolsize is a multiple of ulong
#endif
#define POOLWORDS (POOLSIZE / SIZEOF_UNSIGNED_LONG)
#if SIZEOF_UNSIGNED_LONG == 8
#define ADD_VALUE 0xa5a5a5a5a5a5a5a5
#elif SIZEOF_UNSIGNED_LONG == 4
#define ADD_VALUE 0xa5a5a5a5
#else
#error weird size for an unsigned long
#endif
struct cache {
int len;
int size;
byte *buffer;
};
static int is_initialized;
static struct cache cache[3];
#define MASK_LEVEL(a) do {if( a > 2 ) a = 2; else if( a < 0 ) a = 0; } while(0)
static char *rndpool; /* allocated size is POOLSIZE+BLOCKLEN */
static char *keypool; /* allocated size is POOLSIZE+BLOCKLEN */
static size_t pool_readpos;
static size_t pool_writepos;
static int pool_filled;
static int just_mixed;
static int secure_alloc;
static int quick_test;
static void read_pool( byte *buffer, size_t length, int level );
static void read_dev_random( byte *buffer, size_t length, int level );
static void
initialize()
{
/* The data buffer is allocated somewhat larger, so that
* we can use this extra space (which is allocated in secure memory)
* as a temporary hash buffer */
rndpool = secure_alloc ? m_alloc_secure_clear(POOLSIZE+BLOCKLEN)
: m_alloc_clear(POOLSIZE+BLOCKLEN);
keypool = secure_alloc ? m_alloc_secure_clear(POOLSIZE+BLOCKLEN)
: m_alloc_clear(POOLSIZE+BLOCKLEN);
is_initialized = 1;
}
/****************
* Fill the buffer with LENGTH bytes of cryptologic strong
* random bytes. level 0 is not very strong, 1 is strong enough
* for most usage, 2 is good for key generation stuff but may be very slow.
*/
void
randomize_buffer( byte *buffer, size_t length, int level )
{
for( ; length; length-- )
*buffer++ = get_random_byte(level);
}
byte
get_random_byte( int level )
{
MASK_LEVEL(level);
if( !cache[level].len ) {
if( !is_initialized )
initialize();
if( !cache[level].buffer ) {
cache[level].size = 100;
cache[level].buffer = level && secure_alloc?
m_alloc_secure( cache[level].size )
: m_alloc( cache[level].size );
}
read_pool(cache[level].buffer, cache[level].size, level );
cache[level].len = cache[level].size;
}
return cache[level].buffer[--cache[level].len];
}
/****************
* Mix the pool
*/
static void
mix_pool(byte *pool)
{
char *hashbuf = pool + POOLSIZE;
char *p, *pend;
int i, n;
RMD160_CONTEXT md;
rmd160_init( &md );
#if DIGESTLEN != 20
#error must have a digest length of 20 for ripe-md-160
#endif
/* loop over the pool */
pend = pool + POOLSIZE;
memcpy(hashbuf, pend - DIGESTLEN, DIGESTLEN );
memcpy(hashbuf+DIGESTLEN, pool, BLOCKLEN-DIGESTLEN);
rmd160_mixblock( &md, hashbuf);
memcpy(pool, hashbuf, 20 );
p = pool;
for( n=1; n < POOLBLOCKS; n++ ) {
memcpy(hashbuf, p, DIGESTLEN );
p += DIGESTLEN;
if( p+DIGESTLEN+BLOCKLEN < pend )
memcpy(hashbuf+DIGESTLEN, p+DIGESTLEN, BLOCKLEN-DIGESTLEN);
else {
char *pp = p+DIGESTLEN;
for(i=DIGESTLEN; i < BLOCKLEN; i++ ) {
if( pp >= pend )
pp = pool;
hashbuf[i] = *pp++;
}
}
rmd160_mixblock( &md, hashbuf);
memcpy(p, hashbuf, 20 );
}
}
static void
read_pool( byte *buffer, size_t length, int level )
{
int i;
ulong *sp, *dp;
if( length >= POOLSIZE )
BUG(); /* not allowed */
if( !level ) { /* read simple random bytes */
read_dev_random( buffer, length, level );
return;
}
/* always do a random poll if we need strong numbers */
if( pool_filled && level == 2 )
random_poll();
/* make sure the pool is filled */
while( !pool_filled )
random_poll();
/* do always a fast random poll */
fast_random_poll();
/* mix the pool (if add_randomness() didn't it) */
if( !just_mixed )
mix_pool(rndpool);
/* create a new pool */
for(i=0,dp=(ulong*)keypool, sp=(ulong*)rndpool;
i < POOLWORDS; i++, dp++, sp++ )
*dp = *sp + ADD_VALUE;
/* and mix both pools */
mix_pool(rndpool);
mix_pool(keypool);
/* read the required data
* we use a readpoiter to read from a different postion each
* time */
while( length-- ) {
*buffer++ = keypool[pool_readpos++];
if( pool_readpos >= POOLSIZE )
pool_readpos = 0;
}
/* and clear the keypool */
memset( keypool, 0, POOLSIZE );
}
/****************
* Add LENGTH bytes of randomness from buffer to the pool.
* source may be used to specify the randomeness source.
*/
void
add_randomness( const void *buffer, size_t length, int source )
{
if( !is_initialized )
initialize();
while( length-- ) {
rndpool[pool_writepos++] = *((byte*)buffer)++;
if( pool_writepos >= POOLSIZE ) {
pool_filled = 1;
pool_writepos = 0;
mix_pool(rndpool);
just_mixed = !length;
}
}
}
/********************
* FIXME: move these functions to rand_unix.c
*/
void
random_poll()
{
char buf[POOLSIZE/5];
read_dev_random( buf, POOLSIZE/5, 1 ); /* read /dev/urandom */
add_randomness( buf, POOLSIZE/5, 2);
memset( buf, 0, POOLSIZE/5);
}
void
fast_random_poll()
{
#ifdef HAVE_GETTIMEOFTIME
{ struct timeval tv;
if( gettimeofday( &tv, NULL ) )
BUG();
add_randomness( &tv.tv_sec, sizeof(tv.tv_sec), 1 );
add_randomness( &tv.tv_usec, sizeof(tv.tv_usec), 1 );
}
#else /* use times */
{ struct tms buf;
times( &buf );
add_randomness( &buf, sizeof buf, 1 );
}
#endif
#ifdef HAVE_GETRUSAGE
{ struct rusage buf;
if( getrusage( RUSAGE_SELF, &buf ) )
BUG();
add_randomness( &buf, sizeof buf, 1 );
memset( &buf, 0, sizeof buf );
}
#endif
}
--
Werner
finger gcrypt at ftp.guug.de for GNUPG key
fingerprint = 8489 6CD0 1851 0E33 45DA CD67 036F 11B8 FF3E AA0B
More information about the Gnupg-devel
mailing list