cipher/random.c

   1 /* random.c  -  random number generator
   2  *      Copyright (C) 1998 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 <sys/time.h>
  36 #include <sys/types.h>
  37 #include <sys/stat.h>
  38 #include <unistd.h>
  39 #ifdef  HAVE_GETHRTIME
  40   #include <sys/times.h>
  41 #endif
  42 #ifdef HAVE_GETTIMEOFDAY
  43   #include <sys/times.h>
  44 #endif
  45 #ifdef HAVE_GETRUSAGE
  46   #include <sys/resource.h>
  47 #endif
  48 #include "util.h"
  49 #include "rmd.h"
  50 #include "ttyio.h"
  51 #include "i18n.h"
  52 #include "random.h"
  53 #include "rand-internal.h"
  54 #include "dynload.h"
  55
  56
  57 #ifndef RAND_MAX   /* for SunOS */
  58   #define RAND_MAX 32767
  59 #endif
  60
  61
  62 #if SIZEOF_UNSIGNED_LONG == 8
  63   #define ADD_VALUE 0xa5a5a5a5a5a5a5a5
  64 #elif SIZEOF_UNSIGNED_LONG == 4
  65   #define ADD_VALUE 0xa5a5a5a5
  66 #else
  67   #error weird size for an unsigned long
  68 #endif
  69
  70 #define BLOCKLEN  64   /* hash this amount of bytes */
  71 #define DIGESTLEN 20   /* into a digest of this length (rmd160) */
  72 /* poolblocks is the number of digests which make up the pool
  73  * and poolsize must be a multiple of the digest length
  74  * to make the AND operations faster, the size should also be
  75  * a multiple of ulong
  76  */
  77 #define POOLBLOCKS 30
  78 #define POOLSIZE (POOLBLOCKS*DIGESTLEN)
  79 #if (POOLSIZE % SIZEOF_UNSIGNED_LONG)
  80   #error Please make sure that poolsize is a multiple of ulong
  81 #endif
  82 #define POOLWORDS (POOLSIZE / SIZEOF_UNSIGNED_LONG)
  83
  84
  85 static int is_initialized;
  86 #define MASK_LEVEL(a) do {if( a > 2 ) a = 2; else if( a < 0 ) a = 0; } while(0)
  87 static char *rndpool;   /* allocated size is POOLSIZE+BLOCKLEN */
  88 static char *keypool;   /* allocated size is POOLSIZE+BLOCKLEN */
  89 static size_t pool_readpos;
  90 static size_t pool_writepos;
  91 static int pool_filled;
  92 static int pool_balance;
  93 static int just_mixed;
  94
  95 static int secure_alloc;
  96 static int quick_test;
  97 static int faked_rng;
  98
  99
 100 static void read_pool( byte *buffer, size_t length, int level );
 101 static void add_randomness( const void *buffer, size_t length, int source );
 102 static void random_poll(void);
 103 static void read_random_source( int requester, size_t length, int level);
 104 static int gather_faked( void (*add)(const void*, size_t, int), int requester,
 105                                                     size_t length, int level );
 106
 107
 108 static void
 109 initialize()
 110 {
 111     /* The data buffer is allocated somewhat larger, so that
 112      * we can use this extra space (which is allocated in secure memory)
 113      * as a temporary hash buffer */
 114     rndpool = secure_alloc ? m_alloc_secure_clear(POOLSIZE+BLOCKLEN)
 115                            : m_alloc_clear(POOLSIZE+BLOCKLEN);
 116     keypool = secure_alloc ? m_alloc_secure_clear(POOLSIZE+BLOCKLEN)
 117                            : m_alloc_clear(POOLSIZE+BLOCKLEN);
 118     is_initialized = 1;
 119
 120   #if   USE_RNDLINUX
 121     rndlinux_constructor();
 122   #elif USE_RNDUNIX
 123     rndunix_constructor();
 124   #elif USE_RNDW32
 125   #elif USE_RNDOS2
 126   #elif USE_RNDATARI
 127   #elif USE_RNDMVS
 128   #endif
 129 }
 130
 131 void
 132 secure_random_alloc()
 133 {
 134     secure_alloc = 1;
 135 }
 136
 137
 138 int
 139 quick_random_gen( int onoff )
 140 {
 141     int last;
 142
 143     read_random_source(0,0,0); /* init */
 144     last = quick_test;
 145     if( onoff != -1 )
 146         quick_test = onoff;
 147     return faked_rng? 1 : last;
 148 }
 149
 150
 151 /****************
 152  * Fill the buffer with LENGTH bytes of cryptographically strong
 153  * random bytes. level 0 is not very strong, 1 is strong enough
 154  * for most usage, 2 is good for key generation stuff but may be very slow.
 155  */
 156 void
 157 randomize_buffer( byte *buffer, size_t length, int level )
 158 {
 159     char *p = get_random_bits( length*8, level, m_is_secure(buffer) );
 160     memcpy( buffer, p, length );
 161     m_free(p);
 162 }
 163
 164
 165 int
 166 random_is_faked()
 167 {
 168     if( !is_initialized )
 169         initialize();
 170     return faked_rng || quick_test;
 171 }
 172
 173 /****************
 174  * Return a pointer to a randomized buffer of level 0 and LENGTH bits
 175  * caller must free the buffer.
 176  * Note: The returned value is rounded up to bytes.
 177  */
 178 byte *
 179 get_random_bits( size_t nbits, int level, int secure )
 180 {
 181     byte *buf;
 182     size_t nbytes = (nbits+7)/8;
 183
 184     if( quick_test && level > 1 )
 185         level = 1;
 186     MASK_LEVEL(level);
 187     buf = secure && secure_alloc ? m_alloc_secure( nbytes ) : m_alloc( nbytes );
 188     read_pool( buf, nbytes, level );
 189     return buf;
 190 }
 191
 192
 193 /****************
 194  * Mix the pool
 195  */
 196 static void
 197 mix_pool(byte *pool)
 198 {
 199     char *hashbuf = pool + POOLSIZE;
 200     char *p, *pend;
 201     int i, n;
 202     RMD160_CONTEXT md;
 203
 204     rmd160_init( &md );
 205  #if DIGESTLEN != 20
 206     #error must have a digest length of 20 for ripe-md-160
 207  #endif
 208     /* loop over the pool */
 209     pend = pool + POOLSIZE;
 210     memcpy(hashbuf, pend - DIGESTLEN, DIGESTLEN );
 211     memcpy(hashbuf+DIGESTLEN, pool, BLOCKLEN-DIGESTLEN);
 212     rmd160_mixblock( &md, hashbuf);
 213     memcpy(pool, hashbuf, 20 );
 214
 215     p = pool;
 216     for( n=1; n < POOLBLOCKS; n++ ) {
 217         memcpy(hashbuf, p, DIGESTLEN );
 218
 219         p += DIGESTLEN;
 220         if( p+DIGESTLEN+BLOCKLEN < pend )
 221             memcpy(hashbuf+DIGESTLEN, p+DIGESTLEN, BLOCKLEN-DIGESTLEN);
 222         else {
 223             char *pp = p+DIGESTLEN;
 224             for(i=DIGESTLEN; i < BLOCKLEN; i++ ) {
 225                 if( pp >= pend )
 226                     pp = pool;
 227                 hashbuf[i] = *pp++;
 228             }
 229         }
 230
 231         rmd160_mixblock( &md, hashbuf);
 232         memcpy(p, hashbuf, 20 );
 233     }
 234 }
 235
 236
 237 static void
 238 read_pool( byte *buffer, size_t length, int level )
 239 {
 240     int i;
 241     ulong *sp, *dp;
 242
 243     if( length >= POOLSIZE )
 244         BUG(); /* not allowed */
 245
 246     /* for level 2 make sure that there is enough random in the pool */
 247     if( level == 2 && pool_balance < length ) {
 248         size_t needed;
 249
 250         if( pool_balance < 0 )
 251             pool_balance = 0;
 252         needed = length - pool_balance;
 253         if( needed > POOLSIZE )
 254             BUG();
 255         read_random_source( 3, needed, 2 );
 256         pool_balance += needed;
 257     }
 258
 259     /* make sure the pool is filled */
 260     while( !pool_filled )
 261         random_poll();
 262
 263     /* do always a fast random poll */
 264     fast_random_poll();
 265
 266     if( !level ) { /* no need for cryptographic strong random */
 267         /* create a new pool */
 268         for(i=0,dp=(ulong*)keypool, sp=(ulong*)rndpool;
 269                                     i < POOLWORDS; i++, dp++, sp++ )
 270             *dp = *sp + ADD_VALUE;
 271         /* must mix both pools */
 272         mix_pool(rndpool);
 273         mix_pool(keypool);
 274         memcpy( buffer, keypool, length );
 275     }
 276     else {
 277         /* mix the pool (if add_randomness() didn't it) */
 278         if( !just_mixed )
 279             mix_pool(rndpool);
 280         /* create a new pool */
 281         for(i=0,dp=(ulong*)keypool, sp=(ulong*)rndpool;
 282                                     i < POOLWORDS; i++, dp++, sp++ )
 283             *dp = *sp + ADD_VALUE;
 284         /* and mix both pools */
 285         mix_pool(rndpool);
 286         mix_pool(keypool);
 287         /* read the required data
 288          * we use a readpoiter to read from a different postion each
 289          * time */
 290         while( length-- ) {
 291             *buffer++ = keypool[pool_readpos++];
 292             if( pool_readpos >= POOLSIZE )
 293                 pool_readpos = 0;
 294             pool_balance--;
 295         }
 296         if( pool_balance < 0 )
 297             pool_balance = 0;
 298         /* and clear the keypool */
 299         memset( keypool, 0, POOLSIZE );
 300     }
 301 }
 302
 303
 304 /****************
 305  * Add LENGTH bytes of randomness from buffer to the pool.
 306  * source may be used to specify the randomness source.
 307  */
 308 static void
 309 add_randomness( const void *buffer, size_t length, int source )
 310 {
 311     if( !is_initialized )
 312         initialize();
 313     while( length-- ) {
 314         rndpool[pool_writepos++] = *((byte*)buffer)++;
 315         if( pool_writepos >= POOLSIZE ) {
 316             if( source > 1 )
 317                 pool_filled = 1;
 318             pool_writepos = 0;
 319             mix_pool(rndpool);
 320             just_mixed = !length;
 321         }
 322     }
 323 }
 324
 325
 326
 327 static void
 328 random_poll()
 329 {
 330     read_random_source( 2, POOLSIZE/5, 1 );
 331 }
 332
 333
 334 void
 335 fast_random_poll()
 336 {
 337     static void (*fnc)( void (*)(const void*, size_t, int), int) = NULL;
 338     static int initialized = 0;
 339
 340     if( !initialized ) {
 341         if( !is_initialized )
 342             initialize();
 343         initialized = 1;
 344         fnc = dynload_getfnc_fast_random_poll();
 345     }
 346     if( fnc ) {
 347         (*fnc)( add_randomness, 1 );
 348         return;
 349     }
 350
 351     /* fall back to the generic function */
 352   #if HAVE_GETHRTIME
 353     {   hrtime_t tv;
 354         tv = gethrtime();
 355         add_randomness( &tv, sizeof(tv), 1 );
 356     }
 357   #elif HAVE_GETTIMEOFDAY
 358     {   struct timeval tv;
 359         if( gettimeofday( &tv, NULL ) )
 360             BUG();
 361         add_randomness( &tv.tv_sec, sizeof(tv.tv_sec), 1 );
 362         add_randomness( &tv.tv_usec, sizeof(tv.tv_usec), 1 );
 363     }
 364   #else /* use times */
 365     {   struct tms buf;
 366         times( &buf );
 367         add_randomness( &buf, sizeof buf, 1 );
 368     }
 369   #endif
 370   #ifdef HAVE_GETRUSAGE
 371     {   struct rusage buf;
 372         if( getrusage( RUSAGE_SELF, &buf ) )
 373             BUG();
 374         add_randomness( &buf, sizeof buf, 1 );
 375         memset( &buf, 0, sizeof buf );
 376     }
 377   #endif
 378 }
 379
 380
 381
 382 static void
 383 read_random_source( int requester, size_t length, int level )
 384 {
 385     static int (*fnc)(void (*)(const void*, size_t, int), int,
 386                                                     size_t, int) = NULL;
 387     if( !fnc ) {
 388         if( !is_initialized )
 389             initialize();
 390         fnc = dynload_getfnc_gather_random();
 391         if( !fnc ) {
 392             faked_rng = 1;
 393             fnc = gather_faked;
 394         }
 395         if( !requester && !length && !level )
 396             return; /* init only */
 397     }
 398     if( (*fnc)( add_randomness, requester, length, level ) < 0 )
 399         log_fatal("No way to gather entropy for the RNG\n");
 400 }
 401
 402
 403 static int
 404 gather_faked( void (*add)(const void*, size_t, int), int requester,
 405               size_t length, int level )
 406 {
 407     static int initialized=0;
 408     size_t n;
 409     char *buffer, *p;
 410
 411     if( !initialized ) {
 412         log_info(_("WARNING: using insecure random number generator!!\n"));
 413         tty_printf(_("The random number generator is only a kludge to let\n"
 414                    "it run - it is in no way a strong RNG!\n\n"
 415                    "DON'T USE ANY DATA GENERATED BY THIS PROGRAM!!\n\n"));
 416         initialized=1;
 417       #ifdef HAVE_RAND
 418         srand(make_timestamp()*getpid());
 419       #else
 420         srandom(make_timestamp()*getpid());
 421       #endif
 422     }
 423
 424     p = buffer = m_alloc( length );
 425     n = length;
 426   #ifdef HAVE_RAND
 427     while( n-- )
 428         *p++ = ((unsigned)(1 + (int) (256.0*rand()/(RAND_MAX+1.0)))-1);
 429   #else
 430     while( n-- )
 431         *p++ = ((unsigned)(1 + (int) (256.0*random()/(RAND_MAX+1.0)))-1);
 432   #endif
 433     add_randomness( buffer, length, requester );
 434     m_free(buffer);
 435     return 0; /* okay */
 436 }
 437